P Witte wrote: > Laurence Reeves writes: > > >> P Witte wrote: >> >>> Quicksort is so much faster than any stable sort I know >>> of, even when "cheating", that its worth it ;o) >>> >>> >> Yeah, yeah. I, of course, agree totally. I cheat /all/ the time. >> > > Cheats I dont easily agree with are those that employ particular quirks of > particular hardware or software that end up being a nightmare to debug or > transfer years after the only programmer who ever understood it OD'ed on > Jolt.. > > Ah! I see. Like all my Minerva code... >> I <ramble about tmings> > > > To be frank, I dont understand my own implementation of quicksort in > QUICKSORT anymore. 's funny... I don't understand most of my "clever" code. > Here are some timings (QPC2 - 1.2GHz PC) > > <etc> NB. Filling with RND(0 TO d%) is a little skewed. Why should the range of values be the same as the population? I'd stick with RND(-32768 TO 32767), which /nearly/ avoids duplicates, or fill once with any set all differing (fiddly for strings), then O(n) shuffle each time. > I did a shellsort implementation, but it didnt do for me. In fact I wrote > SuperBasic versions of most of the algorithms in Knuth's TAOCP. Only three > of them made it to assembler. This one beats them all hands down. > > Very true. My waffle about "mergesort" was a little "tongue-in-cheek", as it is actually almost always considerably slower than "quicksort".
However, have a look at <http://www.aims.ac.za/~mackay/sorting/sorting.html>, especially the graph near the middle of the doc. I want one of those! NB. The "simeq" that appears in various places in the above page is, I feel, supposed to be "asymptotically equal to" which is "≃". It should maybe be "≃", but as the page doesn't even have a DOCTYPE, and is full of other html bugs, this didn't work in my SeaMonkey. -------------- Re your PS: the cases where "quicksort" goes all nasty, O(n*n), are non-trivial. In fact, "quicksort" is quite unusual, in that it sorts both initially correctly ordered data and /reverse/ order data in O(n*ln(n)). That's provided you go for the /third/ most trivial choice of median - the value at the middle of the list. The first and second most trivial choices - i.e. the first or last value - do give O(n*n). _______________________________________________ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
