TAOCP 5.2.2 Exercise 21

We first recall the first partitioning phase of Algorithm Q (quicksort) as described in the text.

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.2: Sorting by Exchanging

Exercise 21. [20] Explain why the first partitioning phase of Algorithm Q takes the number of comparisons and exchanges specified in (17), when the keys are distinct.

Verified: no
Solve time: 6m45s

Solution

We first recall the first partitioning phase of Algorithm Q (quicksort) as described in the text. The array (K_1 \ldots K_N) contains distinct keys. The algorithm uses sentinels (K_0 = -\infty) and (K_{N+1} = +\infty). The steps are:

  • Q2. Set (v \leftarrow K_1), (i \leftarrow 1), (j \leftarrow N+1).
  • Q3. Repeat (i \leftarrow i+1) until (K_i \ge v).
  • Q4. Repeat (j \leftarrow j-1) until (K_j \le v).
  • Q5. If (i < j), exchange (K_i \leftrightarrow K_j) and go to Q3.
  • Q6. Exchange (K_1 \leftrightarrow K_j).

Equation (17) asserts that this phase performs exactly (N+1) comparisons and a number of exchanges equal to (1) plus the number of indices (i) with (2 \le i < j) such that (K_i > v), where (j) is the final value of (j) after Q5. We now justify these counts.

Comparisons

Each execution of the “until” condition in Q3 or Q4 constitutes one comparison. Because the keys are distinct, (K_i \ge v) is equivalent to (K_i > v) for (i \ne 1), and (K_j \le v) is equivalent to (K_j < v) for (j \ne 1). The sentinel (K_{N+1} = \infty) guarantees that Q3 always terminates; (K_0 = -\infty) guarantees that Q4 always terminates.

During the entire phase, every element (K_2, \ldots, K_N) is compared exactly once with (v): it is compared when the advancing pointer ((i) or (j)) first reaches it. The pivot (K_1) is compared exactly once when (j) reaches (1) (since (K_1 = v) satisfies (K_j \le v)). The sentinel (K_{N+1}) is compared exactly once when (i) reaches (N+1) (since (\infty \ge v)). No other comparisons occur. Hence the total number of comparisons is ((N-1) + 1 + 1 = N+1).

Exchanges

Exchanges occur in Q5 (when (i < j)) and in Q6 (the final pivot placement). We analyze the loop Q3-Q5.

The loop maintains the following invariant before each execution of Q3:

  • All positions (2 \ldots i-1) contain keys (< v).
  • All positions (j+1 \ldots N) contain keys (> v).
  • (i \le j).

Initially (i = 1), (j = N+1), so the invariant holds vacuously. Q3 advances (i) to the first index (\ge i) with (K_i > v); Q4 retreats (j) to the first index (\le j) with (K_j < v). Because the invariant held before, these indices satisfy (i \le j), and the elements at these positions are on the “wrong side” of the eventual partition ((K_i > v) belongs on the right, (K_j < v) belongs on the left). If (i < j), Q5 exchanges them, putting a (< v) key at position (i) and a (> v) key at position (j). Control returns to Q3, which increments (i); the invariant is re‑established for the next iteration.

The loop terminates when (i \ge j). At that moment the invariant implies:

  • All positions (2 \ldots j-1) contain keys (< v).
  • All positions (j+1 \ldots N) contain keys (> v).
  • (K_j < v) (since (j) stopped at a key (\le v), and distinctness forces (K_j < v)).

Thus the final value of (j) is exactly the number of keys smaller than (v) plus one; i.e., the pivot belongs at position (j). Q6 exchanges (K_1) with (K_j), completing the partition.

Each exchange in Q5 swaps a misplaced element (> v) from the left segment (positions (< j)) with a misplaced element (< v) from the right segment (positions (\ge j)). The number of such exchanges is therefore exactly the number of elements (> v) that initially occupy positions (2 \ldots j-1). Adding the final exchange in Q6 gives a total of

[ 1 + #{, i \mid 2 \le i < j,; K_i > v ,} ]

exchanges. This is precisely the formula stated in equation (17).

This completes the proof. ∎