With all caveats to the "different sorts work best in different
situations/data", posts above, the bare-assed fact of the matter is
that quicksort, WHEN SET UP PROPERLY for the data, will beat any other
general purpose sorting algorithim for anything other than trivial
numbers.
The real problem with Quicksort is that it's "fragile" or "cranky", and
you have to be sure that it isn't being fed data that is ALMOST
completely sorted already. Then it bogs down, badly, since a very poor
pivot point for the sub problems, is chosen.
I've seen test runs where Quicksort was only 2nd or 3rd best, but in
every case, the Quicksort used was second-rate, while the "winners"
were highly optimized. You can't just trust someone else's version
without testing it, either. I recall Microsoft sent out a version with
one of their languages which added an extra line to Quicksort, in it's
innermost loop. Slowed the whole Quicksort version down by 18%.
If your quantity of data is greater than can be sorted internally, then
mergesort may be the best choice, since it can handle any size of data
that you can input into a file and be accessed externally.
I've never had much use for "heapsort", bubble sort, exchange sort, ad
nauseum. Clearly, insertion sort is fastest with data which is very
nearly perfectly sorted, and quicksort is best for everything else, for
internal sorting. Whether it's best to use an "average of three" data
points for the first pivot, depends on your data. It should be
considered, however.
Perhaps that's the biggest disadvantage of Quicksort - you have to know
what the data input will be to set it up properly. And to set it up
properly, you also have to have a good understanding of Quicksort,
itself. It isn't a sorting tool you can just "turn on the faucet" and
the water gushes out, at full speed.
One "pseudo" sorting technique which leaves ALL real sorting programs
in the dust, is "bucket" sorting, or "distribution counting". It only
works on data that is small in it's range, but with the set {1,4,4,2,7}
it just sets up the array answer as 0:0, 1:1, 2:0, 3:0, 4:2, 5:0, 6:0,
7:1, so although NOTHING has been actually sorted, you have the sorted
answer, at hand.
I did mention that bucket sorting is an absolute screamer, didn't I?
<grin, grin> Try it, and you'll be amazed. But then, I'm easily amazed
when I see things like binary search, Quicksort, Alpha-beta, and
"bucket" sort. The concept is so simple - but the execution is so fast!
How about we toast A.J. Hoare? (discoverer of Quicksort). Well done!
I have to say I haven't tried the radix and merge sorting combination
program(s). Save a few suds for them, just in case.
Adak
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
