adak wrote:
> 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.
Radix sort will school even the most heavily optimized quicksort for
strings. You can claim these things about quicksort, but have you
actually run the tests yourself? Or are you simply collecting things
you've read and coming to an incomplete conclusion?
> 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.
Quicksort is very fragile, but you don't have to tailor your data to it
if you've written the algorithm well. A good random or median of 3
partition will minimize your chances of hitting a worst case pivot. A
cutoff and switch to a better algorithm for smaller sets avoids the
overkill of quicksort on a lot of small sets. And you can improve the
speed by leaps and bounds simply by testing to see if the set is
already sorted before doing anything.
Quicksort is still fragile to the point where minor changes could very
likely break the algorithm, but the above improvements fly in the face
of your claims, and it suggests that you've only worked with the basic
quicksort algorithm. Anyone who's worked with quicksort much at all
knows that the basic algorithm sucks, and should only be used as an
example when first learning.
> 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.
Any algorithm can be modified to work externally. I've written external
bubble sorts, quicksorts, and radix sorts. Mergesort is simply the most
obvious choice since it can sort data with nothing more than a
sequential stream of records. That's good because random access files
are rare *and* it takes good advantage of the system cache.
> 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.
And yet, that's precisely what it's sold as and used for. Sorting
libraries often use the optimized form of quicksort that I described
above for non-stable sorting and mergesort for stable sorting. Either
quicksort or the introsort variant, that is. If written properly,
quicksort is everything it claims to be, but it's still not always the
fastest of the general sorting algorithms even for the cases you claim
it to be. Once again I question your experience since you seem to have
a disturbingly biased tunnel vision when it comes to quicksort and its
competition.
> 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.
How is distribution sorting "pseudo"? Sure, if you ignore the assembly
step then nothing is really sorted and the algorithm is a glorified
no-op. But to call the whole of it "pseudo-sorting" suggests a distinct
bias toward comparison sorts. But that makes sense since you have some
strange ideas about quicksort.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
