TAOCP 5.2.2 Exercise 18

Algorithm Q (Hoare’s quicksort) from Section 5.

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.2: Sorting by Exchanging

Exercise 18. ▶ [20] Explain how the computation proceeds in Algorithm Q when all of the input keys are equal. What would happen if the "$<$" signs in steps Q3 and Q4 were changed to "$\le$" instead?

Verified: no
Solve time: 6m31s

Solution

Algorithm Q (Hoare’s quicksort) from Section 5.2.2 uses the sentinels (K_0 = -\infty) and (K_{N+1} = +\infty). The partitioning step for a subarray (R_l \ldots R_r) is:

Q1. If (l \ge r), return.
Q2. Set (i \leftarrow l), (j \leftarrow r+1), (v \leftarrow K_l).
Q3. (i \leftarrow i+1); if (K_i < v), repeat this step.
Q4. (j \leftarrow j-1); if (K_j > v), repeat this step.
Q5. If (i < j), exchange (R_i \leftrightarrow R_j) and go to Q3.
Q6. Exchange (R_l \leftrightarrow R_j).
Q7. Recursively sort (R_l \ldots R_{j-1}) and (R_{j+1} \ldots R_r).

(Steps Q3 and Q4 are the two scans; Q3 uses <, Q4 uses >.)

All keys equal

Assume every key equals (v). Consider a partition call with (l < r).

  • In Q3, (i) starts at (l). The first increment makes (i = l+1). Since (K_{l+1}=v), the condition (K_i < v) is false; the loop stops with (i = l+1).
  • In Q4, (j) starts at (r+1). The first decrement makes (j = r). Since (K_r=v), the condition (K_j > v) is false; the loop stops with (j = r).
  • Because (l+1 \le r) (for (r-l \ge 1)), we have (i < j). Step Q5 exchanges (R_i) and (R_j) (both keys are (v), so the exchange changes nothing) and returns to Q3.
  • The process repeats: (i) increments, (j) decrements, and equal elements are exchanged until (i \ge j). The number of exchanges is (\lfloor (r-l)/2 \rfloor).
  • When the scans terminate, (i) and (j) have crossed near the middle. Step Q6 exchanges (R_l) with (R_j), placing the pivot at position (j \approx (l+r)/2). The partition is balanced.
  • Recursion proceeds on two subarrays of roughly equal size. The total running time is (O(N \log N)), but (\Theta(N \log N)) unnecessary exchanges of equal elements occur.

Changing the inequality signs

The exercise asks what happens if the < signs in steps Q3 and Q4 are changed to ≤. In the algorithm as written, Q3 uses < and Q4 uses >. The natural symmetric modification is to make both scans non‑strict: Q3 becomes while K_i ≤ v and Q4 becomes while K_j ≥ v.

Again assume all keys equal (v). In the modified Q3, the condition (K_i \le v) holds for every real record, so (i) increments until it reaches the sentinel (K_{N+1}=+\infty), where (+\infty \le v) is false. Thus (i) becomes (r+1) (or (N+1) for the whole array). In the modified Q4, the condition (K_j \ge v) holds for every real record, so (j) decrements until it reaches the sentinel (K_0=-\infty), where (-\infty \ge v) is false. Thus (j) becomes (l-1) (or (0)).

Now (i = r+1) and (j = l-1), so (i \ge j). No exchange occurs in Q5. Step Q6 attempts to exchange (R_l) with (R_j), but (j = l-1) is the sentinel position - an invalid operation. Even if an implementation stops the scans at the boundaries (so that (j) stops at (l)), the pivot ends up at the leftmost position, making the left partition empty and the right partition of size (r-l). The recursion then becomes extremely unbalanced, yielding (\Theta(N^2)) time.

If only the < in Q3 is changed to ≤ while Q4 remains >, the left scan runs to the end ((i = r+1)) while the right scan stops immediately ((j = r)). Again (i > j), no exchanges, and the pivot is swapped with (R_r), producing an empty left partition and (O(N^2)) behavior.

Hence, changing the strict inequalities to non‑strict ones destroys the balanced partitioning on equal keys and leads to quadratic worst‑case performance (or an invalid sentinel access).

This completes the proof. ∎