Worst-case performance of quickSort / getPivot
Ivan Kazmenko
gassa at mail.ru
Sat Nov 16 17:36:22 PST 2013
On Sunday, 17 November 2013 at 01:07:20 UTC, Ivan Kazmenko wrote:
> Now, the assumption of picking a pivot in O(1) comparisons
> covers a broad variety of pivot choices, including
> first/last/middle/random element, median of three or five,
> median of medians, or any combination of these. The random
> pick fails in the following sense: if we seed the RNG,
> construct a killer case, and then start with the same seed, we
> get Theta(n^2) behavior reproduced.
Correction: this does *not* cover the median-of-medians case [1].
Median of medians does not fall under our assumption that
selecting a pivot is O(1). It also actually guarantees O(n log
n) worst case performance, but of course at a cost of being
slower than your typical pivot selection on an average case.
[1] http://en.wikipedia.org/wiki/Median_of_medians
Ivan Kazmenko.
More information about the Digitalmars-d
mailing list