9.3-6

The kth quantiles of an n-element set are the k 1 order statistics that divide the sorted set into k equal-sized sets (to within 1). Give an O(n lg k)-time algorithm to list the kth quantiles of a set. The k quantiles of an n-element sorted array A are: A[\floor 1 n/k \rfloor],A[\lfloor 2 · n/k \rfloor], . . . ,A[\lfloor(k − 1) · n/k\rfloor]. We have as inputs an unsorted array A of distinct keys, an integer k, and an empty array Q of length k − 1 and we want to find the kth quantiles of A. QUANTILES(A, k,Q)
1. if k = 1 then return
2. else
3. n = length[A]
4. i = $\lfloor k/2 \rfloor$
5. x = $ SELECT (A, \lfloor i n/k \rfloor)$
6. PARTITION (A, x)
7. Add to list Q: QUANTILES(A[1]..A[i· n/k], \lfoor k/2 \rfloor, Q)
8. Add to list Q: QUANTILES(A[i·n/k + 1]..A[n],\lceil k/2 \rceil, Q)
9. return x
The output Q of the recursive algorithm QUANTILES contains the kth quantiles of A. The algorithm first finds the key that turns out to be the lower median of Q, and then partitions the input array about this key. So we have two smaller arrays that each contain at most (k−1)/2 of the k−1 order statistics of the original array A. At each level of the recursion the number of order statistics in the array is at most half the number of the previous array. Consider a recurrsion tree for this algorithm. At the top level we need to find k − 1 order statistics, and it costs O(n) to find one. The root has two children, one contains at most $\lfoor(k−1)/2\rfloor$ order statistics, and the other $\lceil (k−1)/2 \rceil$ order statistics. The sum of the costs for these two nodes is O(n). At depth i we find $2^i$ order statistics. The sum of the costs of all nodes at depth i is O(n), for $0 \leq i \leq log_{2} (k − 1)$, because the total number of elelements at any depth is n. The depth of the tree is $d = log_{2}(k − 1)$. Hence, the worstcase running time of QAUNTILES is $ \theta(n lg k)$.