|
PureBytes Links
Trading Reference Links
|
> In spite of the comment saying it's a "very fast" sort routine,
> it's not.
Do you know this from experience or are you merely assuming it based on
a mental image of how you think it works? I haven't done any speed
testing myself but I trust Bob Brickey's testing unless I see some
evidence to the contrary. He's really quite good at this kind of thing.
(understatement :-)
FWIW, Brickey calls it an exchange sort, not a bubble sort. Scroll to
the bottom to find his speed testing results. The exchange sort is
clearly faster than either a bubble sort or a heap sort, and by a large
margin. Aw, heck, here are the numbers without scrolling down and
reading the whole thing.
Bubble Sort...: 66.13 Seconds
Insertion Sort: 35.53 Seconds
Heap Sort.....: 27.91 Seconds
Shell Sort....: 16.70 Seconds
Quick Sort....: 6.59 Seconds
Exchange Sort.: 4.61 Seconds
--
Dennis
-------------------------------------------------------------------
I found the original post by Bob Brickey describing this algorithm
with his tests of it. It is appended below. I haven't tested it
myself.
Bob Fulks
----------------
Resent-Date: Fri, 12 Sep 1997 21:35:25 -0700 (PDT)
To: Omega Mailing List <omega-list@xxxxxxxxxxxxxxx>
Subject: Re: Exchange Sorts
Date: Fri, 12 Sep 97 22:33:56 -0500
From: Scientific Approaches <sci@xxxxxxxxxx>
Resent-From: omega-list@xxxxxxxxxx
X-Mailing-List: <omega-list@xxxxxxxxxx> archive/latest/9585
X-Loop: omega-list@xxxxxxxxxx
Precedence: list
Resent-Sender: omega-list-request@xxxxxxxxxx
Earlier today I wrote:
******************
An exchange sort compares each element, starting with the first, with
every following element. If any of the following elements is smaller
than the current element, it is exchanged with the current element
and the process is repeated for the next element. The sort order can
be reversed by starting at the other end and working in the opposite
direction or by exchanging following elements that are larger, rather
than smaller.
That is all there is to it. It can be implemented with a couple
nested "for loops" in just a few lines of code. It is very fast. In
fact, it is many times faster than more complicated methods like
"insertion sorts" or "bubble sorts" that are widely used.
***********************
Paul Altman sent the following message privately, but I am responding
to the list in case others misinterpreted the process I tried to
explain:
Sorry, I must be missing something. This wouldn't work. Let's say you
wanted to sort a 3-element list comprised of 3,2,1. We want it sorted
in ascending order. Starting with the first element as a candidate
for the first exchange, the sort algorithm then looks at the 2nd
element which has a value of 2. The algorithm sees that it is in fact
smaller than element 1 (value=3), so it exchanges it.
We now have a list = 2,3,1.
The algorithm "repeats the process for the next element", which would
result in a list = 2,1,3.
We now approach the 3rd element, and since there are no following
elements, the algorithm does nothing.
We're now stuck with a list = 2,1,3.
Is it possible I misread this or you left out a word or two?
My explanation could have been more clear, but note I said "An
exchange sort compares each element, starting with the first, with
EVERY following element ." Value comparison scans continue through
list elements to the end of the list on each cycle, rather than
ending after one comparison, as in your example.
Using your list example, we would start with:
3,2,1
As you correctly stated, the second element is less than the first,
so the two are exchanged, resulting in:
2,3,1
However, the algorithm does not recycle yet, because the comparison
scan hasn't included "EVERY following element." The next element to
the right is 1, which is less than the current comparison element,
which is 2, so those two elements are exchanged, yielding:
1,3,2
The comparison scan has now reached the end of the list, so the first
comparison reference pointer moves to the second element, which
currently is 3. The 2 to its right has a lower value, so those two
elements are exchanged, resulting in:
1,2,3
which puts the list in ascending order.
I sorted 32,767 randomly ordered FLOATS (seven decimal digit floating
point numbers) tonight on a Pentium/180 using six different popular
sort algorithms written in "C". These are the measured sort times of
each:
Bubble Sort...: 66.13 Seconds
Insertion Sort: 35.53 Seconds
Heap Sort.....: 27.91 Seconds
Shell Sort....: 16.70 Seconds
Quick Sort....: 6.59 Seconds
Exchange Sort.: 4.61 Seconds
As you can see, there are large differences. If you are in a hurry
and starting with randomly ordered values, an Exchange Sort is the
one to use.
-Bob Brickey
Scientific Approaches
sci@xxxxxxxxxx
|