On Sep 8, 2006, at 4:40 PM, Þór Sigurðsson wrote:
-----Original Message-----
On Behalf Of Charles Yeomans
Sent: 8. september 2006 20:18
To: REALbasic NUG
Subject: Re: Listbox sort algorithm ([EMAIL PROTECTED])
What sorts would you want, and why would you want them? 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.
Charles Yeomans
Not neccesarily. Mergesort, while being O(n log n) best case and
most common
case, if the list happens to be already sorted, it is O(n^2) (worst-
case).
If you are using the sort routine for a listbox, you have a user
clicking (
or activating by other means ) the sorting. IF the user activates
the sort
on unsorted data ( lets say a list of 10.000 items ), the sort is
fairly
quick. But if the user activates the sort a second time ( this time
the data
is already sorted ), you could just as well have used bubblesort,
insertionsort or selectionsort. Actually, of the four O(n^2) sorting
algorithms, bubblesort would be most efficient on an already sorted
list,
since that is the one that can be told to exit early ( after one
pass, or
O(n) ) since there where no data to sort.
If you are sorting numerical data, radix sort ( O(n)) may be the most
efficient around.
The problem with sorting routines is that the correct one has to be
chosen
depending on the circumstances. Th choice should of course be put
on the
shoulders of the software engineer desining the application, not the
software engineer that designed the development tool.
/Þór
PS: I didn't mention Heapsort ( O(n log n) ) since that's next on
my class
schedule ;-)
You might need to repeat the earlier class; mergesort is O(n*log n)
at worst, and can be implemented with linear running time at best, as
I do in my SortLibrary.
Charles Yeomans
Charles Yeomans_______________________________________________
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>
