|
PureBytes Links
Trading Reference Links
|
DH
Good info. It is my understanding the array size is 25 elements from looking
at the posts. So
ignoring any descrepancy's caused by initialization time overhead. we can
get an estimate of the execution time
for 25 elements.
32767/25 = 1310
4.61sec/1310 = 3.5 milliseconds
66.13/1310 = 50 milliseconds
In the larger picture it may not make any difference if the routine is only
called once. If not the exchange sort
definitely is a winner.
Jerry
----- Original Message -----
From: "DH" <catapult@xxxxxxxxxxxxxxxxxx>
To: "Omega List" <omega-list@xxxxxxxxxx>
Sent: Sunday, February 08, 2004 2:05 PM
Subject: Re: Minlist, Maxlist (sorting an array)
> > 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
>
|