Oh yes. I've tested several versions of quicksort, against several other algo's. Once Quicksort was tuned, nothing matched it for a general purpose sorter of large N.
If you read through my post, I showed the example on an array of what I was talking about with distribution sorting. Since it actually sorts nothing, but just records the distribution (which we can use in some programs as equivalent to sorting, because it's all we really need), I call it "pseudo sorting". I never meant to imply that distribution sorting couldn't do more - but just that this much is sometimes all we need - and it's BLINDINGLY fast, fast, fast! I'm well aware that any sort can be made to run in an external fashion. I've written a couple versions of it for Quicksort. Unless you have a HUGE amount of RAM, I'm not sure there's any point in trying to beat a natural fit like mergesort, for an external sorter, however. With drive controller's having 8 to 16 megs, commonly - you have to respect that! I am biased toward Quicksort, simply because it has proven itself the best sorter I've ever seen, in test after test, after test. Since strings are just a series of char's, and char's are just numbers, I don't see your point about Quicksort not being good with strings. I read a small book on sorting and searching, (just a paperback, not Knuth or Weiss), years ago. Then we studied them briefly in my two programming language classes. The classes were alright for a lot of things, but that little book on sorting and searching was a marvel, and I learned a ton from it, especially on Quicksort. I find most of the books on algo's, somewhat long on calculating models, and VERY short on meaningful tests on applicable data. It's fine that the author knows some calculus, but can't he also learn how to run practical tests, with meaningful data using some popular languages, on real world PC's? I'm not a CIS major. Just someone who is very glad than my programs don't have to spend HOURS sorting on 8088 hardware, with bubble sort. <grin, grin> Databases were especially poor with this, in those days. Very common to start a job that involved sorting and searching, and having it run uninterrupted all night, and not finish until Noon the next day, even on 80386 hardware. The newer takes on sorting, I'm not up to speed on. I haven't even run a radix sort in the last 10 years, and haven't seen the "radix-mergesort" combo that was mentioned earlier in this thread, at all. That's why I said "save some suds for them - just in case". I agree that Quicksort is promoted as a "one shoe size fits all feet" kind of algo, but that's also what I hear from other programmer's, far too often. They have other, more important fish to fry, and they've thrown in Quicksort, so it's onward and upward... no thought of any tuning or testing for now. (Maybe manana, maybe later, maybe never) Replace "A.J." Hoare, with C.A.R. Hoare, and Sir Tony will be immensely pleased. <grin> A while back I was coding a chess program utility that recorded every board position, in thousands of grand master level chess games. Each postition could be described in a long string, called FEN, something like this (for the starting position of the game): rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RBNQKBNR, with black's pieces being at the top and in lower case. A few more char's describe things like who's turn it is, what castling rights remain for each player, etc. As you might suspect, I quickly wound up with hundreds of thousands of these strings, with hundreds of them being repeated, and needed them to be sorted and the repetitions, removed. So I charge up old Quicksort/mergesort, and off I go. Then I thought. "What the hell, let's see if this Windows 2000 can sort it using it's sort command, in a decent time." What a shock! It was faster than my program. Wasn't even a close race! Looking into it in the help files I found out why. Windows 2000 Pro has dedicated micro-code for sorting, and guarantees sort requests will have certain resources to assist it in a high priority. Well done, Windows 2000! This was NOT my old DOS, believe me!! Marvelous! Adak --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
