Ravindra Ranwala's Blog

Problem statement Exercise 9.3-8 The $k$th 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 \cdot lg k)$-time algorithm to list the $k$th quantiles of a set. [1] Definitions In statistics and probability, quantiles are cut points dividing the range of a probability distribution into continuous intervals with equal probabilities, or dividing the observations in a sample in the same way. There is one fewer quantile than the number of groups created. [2] Approach Let's write a divide and conquer algorithm using selection to solve this problem. What if we find the $l = \lfloor\frac{n \cdot \lfloor\frac{k}{2}\rfloor}{k}\rfloor$ th smallest number  and partition the array around it. Then, we can find the first $\lfloor\frac{k}{2}\rfloor$ cut points in the first half $l$ and the remaining $\lceil\frac{k}{2}\rceil$ cut points in the second half $n - l$. At each step, we keep on dividing $...