TAOCP 5.4.8 Exercise 9
In the elevator problem of Section 5.
Section 5.4.8: Two-Tape Sorting
Exercise 9. ▶ [M25] Find a significant connection between the “cocktail-shaker sort” described in Section 5.2.2, Fig. 16, and the numbers $u_1,u_2,\ldots,u_n$ of (4) in the case $b=1$.
Verified: no
Solve time: 8m35s
Solution
In the elevator problem of Section 5.4.8 (Fig. 88), equation (4) defines for (b=1) (capacity one) the numbers
(u_k = #{\text{passengers on floors } 1,\dots,k \text{ destined for floors } > k})
and (d_{k+1} = #{\text{passengers on floors } > k \text{ destined for floors } \le k}).
When the initial and destination floors form a permutation (\pi) of ({1,\dots,n}) (one passenger per floor), we have
(u_k = |{i \le k : \pi(i) > k}|) and (d_{k+1} = u_k).
The cocktail‑shaker sort (Section 5.2.2, Fig. 16) operates on an array (A[1\dots n]) (here (A = \pi)). It maintains left and right bounds (L) and (R); initially (L=1), (R=n). A left‑to‑right (LTR) pass scans (i) from (L) to (R-1), swapping (A[i]) and (A[i+1]) if (A[i] > A[i+1]). The last index where a swap occurred becomes the new (R). A right‑to‑left (RTL) pass scans downward from (R) to (L+1), swapping (A[i-1]) and (A[i]) if (A[i-1] > A[i]); the smallest such index becomes the new (L). The process alternates until a pass makes no swaps.
Connection.
For a fixed boundary (k) ((1 \le k \le n-1)), let (U_k) be the number of LTR passes that compare (A[k]) and (A[k+1]) (i.e., that have (L \le k < R) at their start), and let (D_k) be the number of RTL passes that compare the same pair. Then
[ U_k = \max(1,, u_k), \qquad D_k = \max(1,, d_{k+1}) = \max(1,, u_k). ]
Consequently the total number of boundary crossings (which measures the running time of the sort) is
[ \sum_{k=1}^{n-1} (U_k + D_k) = 2\sum_{k=1}^{n-1} \max(1,, u_k), ]
exactly the optimal elevator schedule time given in Exercise 6 for (m=1). Thus the cocktail‑shaker sort is the optimal elevator algorithm when the elevator capacity is one.
Proof of (U_k = \max(1, u_k)).
Consider the set (S = {x \in {k+1,\dots,n} : \text{initial position of } x \le k}). These are precisely the elements that must cross boundary (k) from left to right; (|S| = u_k).
During the sort, an element moves right only in LTR passes. The largest element in the unsorted region moves all the way to the right end of that region in a single LTR pass. Because the new (R) is set to the position of that element, the unsorted region shrinks exactly by removing the largest remaining element. By induction on the number of LTR passes, the (j)-th LTR pass crosses boundary (k) if and only if at least (j) elements of (S) are still unsorted. Hence the number of LTR passes that cross boundary (k) equals (|S| = u_k) whenever (u_k > 0). If (u_k = 0), no element needs to cross, but the very first LTR pass still has (R = n > k) and therefore crosses boundary (k). This gives (U_k = \max(1, u_k)).
The argument for RTL passes is symmetric: elements move left only in RTL passes, the set of elements that must cross boundary (k) from right to left has size (d_{k+1} = u_k), and the bound (L) expands rightward as the smallest unsorted elements are placed. Hence (D_k = \max(1, d_{k+1}) = \max(1, u_k)). ∎
This completes the proof. ∎