Linear-time Median
SELECT (A, k)
1. split A into n/5 groups of five elements
2. let bi be the median of the i-th group
3. let B = [b1, b2, …, bn/5]
4. medianB = SELECT (B, B.length/2)
5. rearrange A so that all elements smaller than
medianB come before medianB, all elements
larger than medianB come after medianB, and
elements equal to medianB are next to medianB
6. j = position of medianB in rearranged A
(if more medianB’s, then take the closest
position to n/2)
7. if (k < j) return SELECT ( A[1…j-1], k )
8. if (k = j) return medianB
9. if (k > j) return SELECT ( A[j+1…n], k-j )
SELECT (A, k)
1. split A into n/5 groups of five elements
2. let bi be the median of the i-th group
3. let B = [b1, b2, …, bn/5]
4. medianB = SELECT (B, B.length/2)
5. rearrange A so that all elements smaller than
medianB come before medianB, all elements
larger than medianB come after medianB, and
elements equal to medianB are next to medianB
6. j = position of medianB in rearranged A
(if more medianB’s, then take the closest
position to n/2)
7. if (k < j) return SELECT ( A[1…j-1], k )
8. if (k = j) return medianB
9. if (k > j) return SELECT ( A[j+1…n], k-j )
