-----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 ;-) _______________________________________________ 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>
