On 10/9/10 11:52 CDT, Sean Kelly wrote:
Andrei Alexandrescu Wrote:
In fact, guards can be put to ensure that the _expected_ (not average,
not best-case) complexity is O(n log n). This makes the risk of hitting
a worst-case scenario negligible in a principled manner.
http://en.wikipedia.org/wiki/Quicksort#Randomized_quicksort_expected_complexity
http://docs.google.com/viewer?a=v&q=cache:MdBVR26N5UsJ:www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0123.pdf+randomized+quicksort&hl=en&gl=us&pid=bl&srcid=ADGEESi3GTSxfHWkeb_f14H0pkbigduS94qJVc9XLQ7aPa6lPUJ5JZbggI0izFe3ogiVOJCYcVkGtdumaS9hBvrGw0-TA_yZQj2qd1-AEudKyEWEGXnO4sTwqCZL95OpFkdFHDF2WXFV&sig=AHIEtbT1R0q5RIR4rob17QUKlYVl90vXyQ
Currently std.algorithm.getPivot picks the middle of the range as the
pivot, but I made it modular such that it can be improved in a number of
ways (i.e. randomized, median-of-3, median-of-5, etc).
It would be nice if it used insertion sort for small ranges as well. There's
also a quicksort variant that partitions equal-to elements separately from
less-than and greater-than values, which is faster for ranges with a lot of
equal elements (and no slower for ranges without).
I guess that's "fit pivot" :o). Fat pivot does cost some more.
Andrei
