TAOCP 5.2.2 Exercise 55

In Program Q (Quicksort), step Q3 (lines 4H-6H) chooses the first element of the current subfile as the partitioning element.

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.2: Sorting by Exchanging

Exercise 55. ▶ [22] Show how to modify Program Q so that the partitioning element is the median of three keys (see exercise 28), assuming that $M > 1$.

Verified: no
Solve time: 9m33s

Solution

In Program Q (Quicksort), step Q3 (lines 4H-6H) chooses the first element of the current subfile as the partitioning element. To implement the median‑of‑three improvement (Exercise 28), we replace that step by code that selects the median of the first, middle, and last elements of the subfile, moves it to the first position, and then proceeds with the original partitioning loop.

Let the current subfile have left index i (in rI1) and right index j (in rI2), with j ≥ i+1 (i.e., at least two elements - the exercise’s condition M > 1 refers to the subfile size). The middle index is mid = ⌊(i+j)/2⌋. We compute mid, sort the three keys K_i, K_mid, K_j into nondecreasing order by a sequence of compare‑exchange operations, then swap the median (which ends up at mid) into position i. The median is loaded into rA, stored in PIVOT, and i is incremented to i+1 exactly as in the original program. The rest of Program Q remains unchanged.

The following MIX code replaces lines 4H-6H of Program Q. It uses a temporary memory cell MID to hold the middle index and rI3 as a working register. The original line 7H (CMPA INPUT,1) follows immediately after the new code.

4H  ENT3 0,2        rI3 ← j
5H  SUB3 1,1        rI3 ← j - i
6H  ST3 MID         MID ← j - i
7H  LDA MID
8H  SRA 1           (j - i)/2
9H  ADD 0,1         i + (j - i)/2 = mid
10H STA MID
11H ENT3 MID        rI3 ← mid
12H LDA INPUT,1     rA ← K_i
13H CMPA INPUT,3    compare K_i : K_mid
14H JLE 1F
15H LDX INPUT,3
16H STX INPUT,1
17H STA INPUT,3
18H 1H  LDA INPUT,1     rA ← K_i
19H CMPA INPUT,2    compare K_i : K_j
20H JLE 2F
21H LDX INPUT,2
22H STX INPUT,1
23H STA INPUT,2
24H 2H  LDA INPUT,3     rA ← K_mid
25H CMPA INPUT,2    compare K_mid : K_j
26H JLE 3F
27H LDX INPUT,2
28H STX INPUT,3
29H STA INPUT,2
30H 3H  LDA INPUT,3     rA ← median
31H LDX INPUT,1     rX ← minimum
32H STX INPUT,3
33H STA INPUT,1     median now at position i
34H STA PIVOT       store pivot
35H INC1 1          i ← i + 1

Verification.
After line 11, rI3 = mid. Lines 12-17 ensure K_i ≤ K_mid; lines 18-23 ensure K_i ≤ K_j; lines 24-29 ensure K_mid ≤ K_j. Hence the three keys are sorted: K_i ≤ K_mid ≤ K_j. The median is K_mid. Lines 30-33 swap K_i and K_mid, placing the median at position i and the minimum at mid. Line 33 leaves the median in rA; line 34 stores it in PIVOT; line 35 increments i to i+1. The original line 7H (CMPA INPUT,1) now finds the pivot in rA and the scanning index i correctly set to l+1.

For a subfile of size 2, mid = i; the first and third comparisons are with the same element and have no effect, while the second comparison correctly orders the two distinct keys. The median of the three (with one duplicate) is the smaller of the two distinct keys, which is a valid pivot. The algorithm’s asymptotic complexity is unchanged because only a constant number of extra instructions are executed per partitioning step.

This completes the construction. ∎

Notes

The condition “M > 1” in the exercise statement refers to the size of the current subfile (denoted by M in the surrounding discussion of Algorithm Q). The modification assumes the subfile contains at least two elements; subfiles of size 0 or 1 are handled by the stack‑management logic of Program Q before step Q3 is reached.