[EMAIL PROTECTED] wrote: > [EMAIL PROTECTED] wrote: > > <SNIP> > >> OK. So the random order - quicksort marginally outperforms heapsort. For >> the already sorted case, quicksort is rather better than heapsort, but >> its margin goes down as the count goes up. However, with the data all >> the same... ooopppsss.... my quicksort has fallen headlong into the >> O(n*n) trap. >> > > That has always been a 'failing' of the quicksort, when the data are in > sorted order, it takes 'forever' to finish. I was taught that at college and > was reminded of it when I wrote "PrinterMaster 2" - I used a quicksort > internally and if it was run twice, the first one was quick (the data were > random) and the second took ages (the data were sorted already). > > In the end, I ripped the guts of the quicksort out and replaced it with some > other sort, probably a bubble sort as I think the size of the array being > sorted was limited to 200 entries or something. Then again, maybe I used > something else instead. > > In reply to Per's comments earlier, as Norman in effect says, quicksort is *not* a good all-rounder. It is fast, but in order to be happy with that speed, you must accept a stack that grows to O(ln(n)) (O(n) with buggy code!) and the /guarantee/ that some data will take O(n*n) to sort.
BTW. Quicksort does not, in principle, mind data that is initially sorted. Its /simplest/ implementation, which uses the first item as the median, has that problem. Ditto for using the last item. Just using the middle item gets around that, but in reality just hides the root problem: the worst case is always O(n*n). You are quite right to point out that bubblesort is maligned for all the wrong reasons. Even with 200 items, where the n/ln(n) means you should expect the sorting to take of the order of a 38 longer, if that means 38 microseconds, instead of one microsecond... In fact, in a genuinely real time application, given the choice of using one or the other, you would have choose bubblesort. When quicksort /does/ hit an O(n*n) case, it takes /vastly/ longer than bubblesort. _______________________________________________ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
