The selection problem: Given a set of n elements, find the ith smallest element from the set, where 1 ≤ i ≤ n.
- Find the i-th largest element in A
= find the (n ? i + 1)-th smallest element in A - 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 -
Find the first i largest elements in A
An algorithm for general selection
The partitioning step can be done in O(n) time.
- The overall performance of the algorithm depends on the choice of the pivot element x.
- In the worst case, the total time might be Θ(n^2). (Consider if i = 1 and x is always the largest element.)
- It can be shown that if x is chosen at random, then the average time is O(n).
