Selection Problem

Internal

• Data Structures and Algorithms
• Sorting Algorithms

Overview

The i^th order statistic of a set of n numbers is the i^th smallest number in the set.

Finding the i^th order statistic of a set of n distinct numbers is known as the selection problem. Finding the median is a particular case of the selection problem. The selection problem can be resolved generically by sorting the entire set and then selecting the desired element. However, key comparison sorting cannot be done more efficiently than Ω(n lgn), and more specialized and faster algorithms exist.

The general selection problem can be resolved with a randomized divide-and-conquer algorithm with an expected running time of Θ(n).

TODO CLRS page 213.