On the median-of-k version of Hoare's selection algorithm
Institut für Mathematische Stochastik,
Postfach 60 09,
30060 Hannover, Germany; email@example.com.
Accepted: March 1999
In Hoare's (1961) original version of the algorithm the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set S in question. Here we consider a variant where this element is the median of a sample of size 2k+1 from S. We investigate convergence in distribution of the number of comparisons required and obtain a simple explicit result for the limiting average performance of the median-of-three version.
Mathematics Subject Classification: 68Q25 / 68P10
Key words: Randomized algorithms / average performance / asymptotic distribution.
© EDP Sciences, 1999