Sorry, as I already answered Joe, I got Merge and Quick mixed up ( notice how I didn't mention Quick ? :) )
/Þór -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Charles Yeomans Sent: 8. september 2006 21:27 To: REALbasic NUG Subject: Re: Listbox sort algorithm ([EMAIL PROTECTED]) 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> _______________________________________________ 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>
