Order statistics

Order statistics

1. Exercises 9.1-2: Find the second smallest of n elements. (n + ceiling(lgn) - 2 comparisons in the worst case)

2. RANDOMIZED-SELECT: divide and conquer using RANDOMIZED-PARTITION. average: Theta(nlgn), worst: n^2

3. SELECT: divide the array into floor(n/5) groups of 5 elements each and find median of each group using insertion sort; use SELECT recursively to find the median x of these medians; partition the input array around the median-of-medians x; use SELECT recessively on one side of the partition

4. Exercises 9.3-6: list the kth quantiles of a set in O(nlgk). (use divide and conquer)

5. Exercises 9.3-8: find the median of two n elements sorted arrays in O(lgn). (cut the smaller and larger quarters each time)

6. Problem 9-2: post-office location problems in 1-dimension and two dimensions (in Manhattan distance)