On Sep 8, 2006, at 3:17 PM, Charles Yeomans wrote:
For a Listbox, a stable sort is pretty clearly the way to go, and
mergesort is as far as I know the best choice for a stable
comparison-exchange sort.
I am certainly no sorting expert. I assume STABLE means that the sort
will not fail in sorting the given array. I see the MERGE sort
mentioned over and over again on the RB lists and I wonder why it is
so preferred.
A long time ago I wrote a couple of programs related to sorting
algorithms and each time I get a new programming lanugage they are
rewritten in that language. One shows the sorting as an animation on
the screen with the series of bars moving just as the elements values
in the array would be moved during the soret. The other is simply to
time the speed of the various sorts. I use 12 different sort
algorithms. Out of those 12 I find that the Merge sort is typically
the 6th fastest sort being beaten by Shell, Heap, Shell/Insertion,
Comb and Quick. I have heard that under certain circumstances the
Quick sort can be problematic but I have never had any of the 12
sorts not sort a given array.
As an example of the speeds here are the times for a 25,000 element
integer array running an a 2.3 Ghz G5. The times are in milliseconds.
All the leading zeroes are simply to get things to line up nicely in
case you are using proportional fonts. Makes it a little easier to
view. These are listed from slowest to fastest typical sort speed.
For any given set of data this will not always be the order.
13722.995 Bubble
12373.135 Brute Force
11307.910 BiDirectional Bubble
08160.171 Exchange
06879.484 Shaker
04849.349 Insertion
03310.688 Merge
00125.929 Shell
00046.466 Shell/Insertion
00035.271 Heap
00031.419 Comb
00021.703 Quick
The Brute Force sort was given that name by me. It is the first sort
I ever learned. I was taught the technique but not the name so I
never new the proper name for the sort.
So, Merge has a decent speed but certainly is not the fastest. And,
like I said, I have never had any of these fonts fail sorting
integers, singles, doubles, strings. Unless I need the absolute
fastest speed, I usually use the Comb sort in my programs. One time,
and only one time, I had all 12 sorts sort a 250,000 element integer
array. It took just under two hours for all 12 sorts to complete with
the last 5 sorts show above taking less than 5 seconds of that total
time.
=== A Mac addict in Tennessee ===
_______________________________________________
Unsubscribe or switch delivery mode:
<http://www.realsoftware.com/support/listmanager/>
Search the archives of this list here:
<http://support.realsoftware.com/listarchives/lists.html>
