Chapter Objectives

• ith order statistic is the ith smallest element of a set of n elements.
• The minimum is the first order statistic (i = 1).
• The maximum is the nth order statistic (i = n).
• A median is the “halfway point” of the set.
• When n is odd, the median is unique, at i = (n + 1)/2.
• When n is even, there are two medians:
• The lower median, at i = n/2, and
• The upper median, at i = n/2 + 1.
• We mean lower median when we use the phrase “the median.”

The selection problem:

Input: A set A of n distinct numbers and a number i , with 1 ≤ i ≤ n.
Output: The element x ∈ A that is larger than exactly i − 1 other elements in A.
In other words, the ith smallest element of A.

The selection problem can be solved in O(n lg n) time.

• Sort the numbers using an O(n lg n)-time algorithm, such as heapsort or merge sort.
• Then return the ith element in the sorted array.

There are faster algorithms, however.

• First, we’ll look at the problem of selecting the minimum and maximum of a set of elements.
• Then, we’ll look at a simple general selection algorithm with a time bound of O(n) in the average case.
• Finally, we’ll look at a more complicated general selection algorithm with a time bound of O(n) in the worst case.