Laurence Reeves writes: >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...
It did occur to me ;o) although that is not what I mean. (Just go careful on the Jolt, eh) >>> 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. Did that. Added to the given program: .. etc MATFILL a%, 0, 1: Shuffle a% .. QUICKSORT a% .. etc By Shuffle I mean: : DEFine PROCedure Shuffle(array%) LOCal i%, t%, r% FOR i% = 0 TO DIMN(array%) r% = RND(0 to DIMN(array%)) REMark Swap elements t% = array%(i%) array%(i%) = array%(r%) array%(r%) = t% END FOR i% END DEFine : As you probably knew (but are too pedantic to admit ;o) there is no difference to the result at this resolution. Perhaps when one gets into mega sorts any differences really kick in.. >> 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. ≃ doesnt parse at all in IE7. Ive no idea what he means. > 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). Mine uses the median. Following your links took me to Wikipedia and other wierd places. Great that so much information, including complete algorithms in C and other languages (as opposed to Knuth's idiosyncratic (but servicable!) notation) is available so easily nowadays. I wish that were the case when I was trying to work it all out! Per _______________________________________________ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
