Improved randomized selection

Abstract

We show that several versions of Floyd and Rivest's improved algorithm Select for finding the $k$th smallest of $n$ elements require at most $n+\min \{k,n-k\}+O(n^{1/2}{\ln }^{1/2}n)$ comparisons on average and with high probability. This rectifies the analysis of Floyd and Rivest, and extends it to the case of nondistinct elements. Encouraging computational results on large median-finding problems are reported.

14 pages

References in corpus (2)

• Partitioning schemes for quicksort and quickselect
• Randomized selection with quintary partitions