On the median-of-k version of Hoare's selection algorithm
Rudolf Grübel (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
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 in question. Here we consider a variant where this element is the median of a sample of size from . 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.