TAOCP 5.2.2 Exercise 17
In Algorithm Q (Quicksort), the sentinel values \(K_0 = -\infty\) and \(K_{N+1} = +\infty\) (postulated in equation (12)) are used in the two scanning loops of the partitioning phase.
Section 5.2.2: Sorting by Exchanging
Exercise 17. ▶ [20] Where in Algorithm Q do we use the fact that $K_0$ and $K_{N+1}$ have the values postulated in (12)?
Verified: no
Solve time: 1m23s
Solution
In Algorithm Q (Quicksort), the sentinel values (K_0 = -\infty) and (K_{N+1} = +\infty) (postulated in equation (12)) are used in the two scanning loops of the partitioning phase.
During partitioning we choose a pivot (v) and maintain indices (i) and (j) that move toward each other. The algorithm contains the following steps (using the book’s notation):
- Increase (i): Repeatedly set (i \leftarrow i+1) until (K_i \ge v).
- Decrease (j): Repeatedly set (j \leftarrow j-1) until (K_j \le v).
The sentinel (K_{N+1}=+\infty) guarantees that the first loop always terminates: when (i) reaches (N+1), we have (K_{N+1}=+\infty \ge v). Similarly, the sentinel (K_0=-\infty) guarantees that the second loop always terminates: when (j) reaches (0), we have (K_0=-\infty \le v). Without these sentinel values, explicit boundary tests ((i \le N) and (j \ge 1)) would be required inside the loops.
This completes the proof. ∎