TAOCP 5.2.2 Exercise 31

We adapt Algorithm Q (quicksort) to find the $m$th smallest element ($1 \le m \le n$) of a file of $n$ distinct elements.

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.2: Sorting by Exchanging

Exercise 31. [20] (V. A. R. Sarju.) Suppose that, instead of sorting an entire file, you only want to determine the $m$th smallest of $n$ elements. Show that quicksort can be adapted to this purpose, avoiding many of the computations required to do a complete sort.

Verified: no
Solve time: 22m14s

Solution

Algorithm

We adapt Algorithm Q (quicksort) to find the $m$th smallest element ($1 \le m \le n$) of a file of $n$ distinct elements. The idea is to stop the recursion as soon as the pivot element is the $m$th smallest; otherwise we recurse only on the partition that contains the desired element.

Algorithm QS (Quickselect).
Given $n$ records $R_1,\dots,R_n$ with keys $K_1,\dots,K_n$ and an integer $m$ ($1\le m\le n$), this algorithm rearranges the records so that the record with the $m$th smallest key ends up in position $R_m$, and it returns that record. The other records are partitioned around it (all keys to the left are $\le K_m$, all to the right are $\ge K_m$).

QS1. [Initialize.] Set $\mathit{LO}\leftarrow 1$, $\mathit{HI}\leftarrow n$. (The current subfile is $R_{\mathit{LO}}\dots R_{\mathit{HI}}$; we seek the $m$th smallest element of this subfile.)

QS2. [Partition.] If $\mathit{LO} \ge \mathit{HI}$, the subfile has size $\le 1$; terminate with $R_{\mathit{LO}}$ as the answer. Otherwise choose a pivot (e.g., $R_{\mathit{LO}}$) and partition the subfile into three parts: $$R_{\mathit{LO}}\dots R_{k-1}; (<\text{pivot}),\quad R_k; (\text{pivot}),\quad R_{k+1}\dots R_{\mathit{HI}}; (>\text{pivot}).$$ This is done exactly as in Algorithm Q, using $n' = \mathit{HI}-\mathit{LO}+1$ elements and requiring $n'-1$ comparisons. Let $k$ be the final position of the pivot.

QS3. [Test pivot.] If $k = \mathit{LO}+m-1$, the pivot is the desired element; terminate with $R_k$.
If $k > \mathit{LO}+m-1$, the desired element lies in the left partition. Set $\mathit{HI} \leftarrow k-1$ and go to QS2.
If $k < \mathit{LO}+m-1$, the desired element lies in the right partition. Set $m \leftarrow m - (k-\mathit{LO}+1)$, $\mathit{LO} \leftarrow k+1$, and go to QS2. ∎

Correctness Proof

We prove by induction on the size $N = \mathit{HI}-\mathit{LO}+1$ of the current subfile that the algorithm always terminates with the $m$th smallest element of that subfile.

Base case $N \le 1$. If $N=1$, the only element is trivially the $m$th smallest (with $m=1$). The algorithm terminates at QS2.

Inductive step. Assume the algorithm works for all subfiles of size $< N$. For a subfile of size $N \ge 2$, step QS2 partitions it around a pivot that ends up at position $k$. By the properties of partitioning (Algorithm Q), all elements to the left of $k$ are smaller than the pivot, and all to the right are larger. Hence the pivot is the $(k-\mathit{LO}+1)$st smallest element of the subfile.

  • If $k-\mathit{LO}+1 = m$, the pivot is exactly the $m$th smallest; QS3 terminates correctly.
  • If $k-\mathit{LO}+1 > m$, the $m$th smallest lies in the left partition (size $k-\mathit{LO}$). The recursive call (QS3 with $\mathit{HI}\leftarrow k-1$) searches for the $m$th smallest in that partition. By the induction hypothesis it succeeds.
  • If $k-\mathit{LO}+1 < m$, the $m$th smallest lies in the right partition (size $\mathit{HI}-k$). Its rank within that partition is $m - (k-\mathit{LO}+1)$. The recursive call (QS3 with updated $\mathit{LO},m$) searches for this rank in the right partition. By the induction hypothesis it succeeds.

In all cases the subfile size strictly decreases, so the algorithm terminates. This completes the proof. ∎

Average‑Case Analysis

Assume the input is a random permutation of $n$ distinct keys and the pivot is chosen uniformly (e.g., the first element of the current subfile). Partitioning a subfile of size $s$ requires $s-1$ comparisons (each non‑pivot element is compared once with the pivot).

Let $C(n,m)$ be the expected number of comparisons to find the $m$th smallest of $n$ elements. Conditioning on the rank $k$ of the pivot ($1\le k\le n$, equally likely) gives the recurrence $$C(n,m) = n-1 + \frac{1}{n}\biggl(\sum_{k=1}^{m-1} C(n-k,,m-k) + \sum_{k=m+1}^{n} C(k-1,,m)\biggr), \qquad C(1,1)=0. \tag{1}$$

Special case $m=1$ (minimum). The recurrence reduces to $$C(n,1) = n-1 + \frac{1}{n}\sum_{k=2}^{n} C(k-1,1).$$ Solving (e.g., by telescoping) yields $$C(n,1) = 2n - 2H_n = 2n - 2\ln n + O(1).$$ By symmetry $C(n,n) = C(n,1)$.

General $m$. One can show that $C(n,m) \le 4n$ for all $m$ (the worst case is $m \approx n/2$). A more precise asymptotic for fixed $m$ is $C(n,m) \sim 2n$. For $m = \alpha n$ ($0<\alpha<1$), $C(n,\alpha n) \sim c(\alpha)n$ where $c(\alpha) = -2\alpha\ln\alpha - 2(1-\alpha)\ln(1-\alpha)$; the maximum $c(1/2)=2\ln 2 \approx 1.386$ gives $C(n,\lfloor n/2\rfloor) \sim 2n\ln 2 \approx 1.386n$.

Comparison with full quicksort. The average number of comparisons to sort $n$ elements completely is $2(n+1)H_n - 4n \sim 2n\ln n$. Quickselect therefore reduces the work from $\Theta(n\log n)$ to $\Theta(n)$, avoiding many computations. ∎

Final remark. The algorithm above uses the partitioning step of Algorithm Q unchanged; only the recursion is restricted to the relevant partition. The MIX implementation is obtained from Program Q by replacing the two recursive calls with a conditional jump to the appropriate partition.