"Stable" means that the relative order of equal keys is preserved
under sorting. You might compare my implementation of mergesort in
SortLibrary.
Charles Yeomans
On Sep 8, 2006, at 7:04 PM, Harrie Westphal wrote:
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>
_______________________________________________
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>
