Sorry, of course I am. It's Quicksort that splits the array at first found. My bad ;-)
Mergesort is always n log n.. Heh.. The price of currently studying these algorithms, something's gotta get mixed up :-) But I still stand by that the implementation should best be left to the developer of the application. There could be an n log n algorithm like mergesort, but that should be overloadable by the developer ( I don't know if it is, or isn't so don't flame me :) ) /Þór -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Malcolm Smith Sent: 8. september 2006 20:55 To: REALbasic NUG Subject: Re: Listbox sort algorithm ([EMAIL PROTECTED]) On Sep 8, 2006, at 1: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). I think you are confusing Mergesort with Quicksort. Mergesort has an O(n log n) upper bound but QuickSort can have a worst case O(n^2) running time triggered by sorted data. It is not hard to modify QuickSort so that the sorted data does not trigger the worst case though, so it is really only a problem with naive implementations. Of course you could still get pathologically ordered data which slowed down even a smart Quicksort, but I don't mind taking that risk. Living on the edge, that's me! ;) Malcolm > 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> _______________________________________________ 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>
