TAOCP 5.2.2 Exercise 41

Section 5.2.2: Sorting by Exchanging

Exercise 41. ▶ [30] Devise a good way to exchange records $R_l \ldots R_r$ so that they are partitioned into three blocks, with (i) $K_i \le K$ for $l \le k < i$; (ii) $K_i = K$ for $i \le k \le j$; (iii) $K_k > K$ for $j < k \le r$. Schematically, the final arrangement should be

$< K$	$= K$	$> K$
$l$	$i \qquad j$	$r$

Verified: no
Solve time: 6m55s

Setup

We are given a sequence of records (R_l, R_{l+1}, \ldots, R_r) ((1 \le l \le r \le N)) with keys (K_l, K_{l+1}, \ldots, K_r), and a distinguished key value (K). We wish to rearrange the records in place so that they form three contiguous blocks:

all records with key (< K),
all records with key (= K),
all records with key (> K).

The algorithm should output indices (i) and (j) ((l \le i \le j+1 \le r+1)) such that [ K_x < K ;\text{ for }; l \le x < i,\qquad K_x = K ;\text{ for }; i \le x \le j,\qquad K_x > K ;\text{ for }; j < x \le r. ]

Solution

We present Algorithm T (Three-way partition), a variant of the “Dutch national flag” algorithm. It uses three pointers:

(i): the first position of the “(=K)” block (initially (l));
(p): the current scanning position (initially (l));
(j): the last position of the “(=K)” block (initially (r)); the “(>K)” block occupies positions (j+1 \ldots r).

The algorithm maintains the following loop invariant at the start of each iteration (i.e., at step T2):

For (l \le x < i): (K_x < K).
For (i \le x < p): (K_x = K).
For (j < x \le r): (K_x > K).
The segment (p \le x \le j) contains records whose keys have not yet been classified (the “unknown” region).

Algorithm T (Three-way partition).

T1. [Initialize.] Set (i \leftarrow l), (p \leftarrow l), (j \leftarrow r).

T2. [End of loop?] If (p > j), terminate. The partition is complete with boundaries (i) and (j).

T3. [Compare (K_p : K).] If (K_p < K), go to T4; if (K_p = K), go to T5; if (K_p > K), go to T6.

T4. [Move to (<K) region.] Exchange (R_p \leftrightarrow R_i). Set (i \leftarrow i+1), (p \leftarrow p+1). Go to T2.

T5. [Already in (=K) region.] Set (p \leftarrow p+1). Go to T2.

T6. [Move to (>K) region.] Exchange (R_p \leftrightarrow R_j). Set (j \leftarrow j-1). (Do not change (p).) Go to T2.

Correctness. The invariant holds initially because all regions are empty except the unknown region which is the whole array. We check the three branches:

T4 ((K_p < K)): The record at (p) belongs in the (<K) block. Swapping it with (R_i) places it at the end of the (<K) block (position (i)). The record that was at (i) (if (i < p), it was in the (=K) block; if (i = p), it is the same record) moves to (p). Incrementing both (i) and (p) extends the (<K) block by one and shifts the (=K) block right by one, preserving the invariant.
T5 ((K_p = K)): The record at (p) already belongs in the (=K) block. Simply incrementing (p) moves it from the unknown region into the (=K) region.
T6 ((K_p > K)): The record at (p) belongs in the (>K) block. Swapping it with (R_j) places it at the beginning of the (>K) block (position (j)). The record brought from (j) to (p) is unexamined, so we must not advance (p); we only decrement (j), shrinking the unknown region from the right. The invariant is preserved.

Termination follows because each iteration either increases (p) (T4, T5) or decreases (j) (T6), so (p - j) strictly increases. Initially (p - j = l - r \le 0); after at most (r-l+1) iterations we have (p > j).

Complexity. Exactly (r-l+1) comparisons are performed (one per element when it first becomes the scanning element). At most (r-l+1) exchanges occur (each iteration does at most one exchange). The algorithm uses (O(1)) extra space and runs in (O(r-l+1)) time.

[ \boxed{\text{Algorithm T (Three-way partition) as described above solves the problem.}} ]

Verification

The most failure-prone part is the handling of the (>K) case (T6), where (p) is not incremented after swapping with (R_j). An error here would cause the element swapped in from the right to be skipped. We verify this by testing a boundary case that forces multiple T6 steps followed by a T4 step, ensuring the element brought from the right is correctly processed.

Consider (l=1), (r=5), (K=5), and initial keys ([7, 3, 5, 9, 2]) (the correct final blocks are (<5): ({3,2}); (=5): ({5}); (>5): ({7,9})). We trace the algorithm:

Step	(i)	(p)	(j)	Array	Action
T1	1	1	5	([7,3,5,9,2])	init
T3				(K_1=7>5)	T6
T6	1	1	4	([2,3,5,9,7])	swap (R_1\leftrightarrow R_5), (j\leftarrow4)
T3				(K_1=2<5)	T4
T4	2	2	4	([2,3,5,9,7])	swap (R_1\leftrightarrow R_1), (i\leftarrow2), (p\leftarrow2)
T3				(K_2=3<5)	T4
T4	3	3	4	([2,3,5,9,7])	swap (R_2\leftrightarrow R_2), (i\leftarrow3), (p\leftarrow3)
T3				(K_3=5=5)	T5
T5	3	4	4	([2,3,5,9,7])	(p\leftarrow4)
T3				(K_4=9>5)	T6
T6	3	4	3	([2,3,5,7,9])	swap (R_4\leftrightarrow R_4), (j\leftarrow3)
T2				(p=4 > j=3)	terminate

Final boundaries: (i=3), (j=3). The array is ([2,3,5,7,9]).

(<5): positions (1\ldots 2) → ({2,3}).
(=5): position (3) → ({5}).
(>5): positions (4\ldots 5) → ({7,9}).

This matches the specification. The trace confirms that after a T6 step the new element at (p) (here (2) after the first T6) is immediately examined in the next iteration and correctly placed.

As an independent check, we also verify the single-element boundary cases ((l=r)):

If (K_l < K): T4 makes (i=l+1), (p=l+1), then (p>j=l); result (i=l+1), (j=l) gives (<K) block (l\ldots l).
If (K_l = K): T5 makes (p=l+1), then (p>j=l); result (i=l), (j=l) gives (=K) block (l\ldots l).
If (K_l > K): T6 makes (j=l-1), then (p=l>j); result (i=l), (j=l-1) gives (>K) block (l\ldots l).

All are correct.

This completes the verification. ∎

Notes

Algorithm T is a classic three-way partition (Dijkstra’s Dutch national flag). It is optimal in the number of comparisons and uses at most one exchange per element. It can be directly substituted into radix exchange sort (Algorithm R) or quicksort to handle equal keys efficiently, as suggested in Exercise 40.