A probabilistic analysis of the Floyd–Rivest expected time selection algorithm

Abstract

We present a probabilistic analysis of the Floyd–Rivest expected time selection algorithm. In particular, we show that a refinement of the bootstrapped version of the Floyd–Rivest algorithm that determines the Cth order statistic by performing an expected n+C+O (n ^1/2) comparisons can be made into a randomized algorithm that performs n+C+O(n ^1/2 log^3/2 n) comparisons with probability at least 1−1/n ^ρ, for any constant ρ>0.

Keywords:

• Randomization
• Algorithms
• Selection
• Floyd–Rivest selection algorithm