6. The Selection Problem

The selection problem: Given a set of n elements, find the ith smallest element from the set, where 1 ≤ i ≤ n.

1. Find the i-th largest element in A
   = find the (n − i + 1)-th smallest element in A
2. Find the first i smallest elements in A
   find the i-th smallest element x in A, followed by scanning the sequence
   and picking any element y ≤ x when the number of picked elements is no larger than i

3. Find the first i largest elements in A

   
   An algorithm for general selection

The partitioning step can be done in O(n) time.

1. The overall performance of the algorithm depends on the choice of the pivot element x.
2. In the worst case, the total time might be Θ(n^2). (Consider if i = 1 and x is always the largest element.)
3. It can be shown that if x is chosen at random, then the average time is O(n).