TAOCP 5.2.2 Exercise 9

Section 5.2.2: Sorting by Exchanging

Exercise 9. [M48] Analyze the number of passes and the number of comparisons in the cocktail-shaker sorting algorithm. Note: See exercise 5.4.8–9 for partial information.

Verified: no
Solve time: 33m58s

Setup

The cocktail-shaker sort (also called bidirectional bubble sort) operates on a file of (N) records (R_1,\dots,R_N) with distinct keys (K_1,\dots,K_N). The algorithm maintains two bounds (L) and (R) delimiting the unsorted portion; initially (L=1), (R=N). It alternates a forward pass (left‑to‑right) and a backward pass (right‑to‑left) until a complete pass makes no exchanges.

Algorithm C (Cocktail-shaker sort).

Set (L \leftarrow 1), (R \leftarrow N).
Forward pass. Set (t \leftarrow 0). For (j = L, L+1, \dots, R-1): if (K_j > K_{j+1}) then interchange (R_j \leftrightarrow R_{j+1}) and set (t \leftarrow j). If (t = 0) terminate. Otherwise set (R \leftarrow t).
Backward pass. Set (t \leftarrow 0). For (j = R, R-1, \dots, L+1): if (K_{j-1} > K_j) then interchange (R_{j-1} \leftrightarrow R_j) and set (t \leftarrow j). If (t = 0) terminate. Otherwise set (L \leftarrow t).
Go to step 2.

We assume the input is a random permutation of ({1,2,\dots,n}) (where (n=N)). A pass is one execution of step 2 or step 3. A comparison is each evaluation of (K_i > K_{i+1}) (or (K_{i-1} > K_i)) inside the loops.

To analyse the algorithm we use inversion tables. For a permutation (a_1\dots a_n) and each value (k\in{1,\dots,n}) define

[ b_k = #{,i < \operatorname{pos}(k) \mid a_i > k,},\qquad c_k = #{,i > \operatorname{pos}(k) \mid a_i < k,}. ]

(b_k) is the number of larger elements preceding (k) (the “forward” inversion table); (c_k) is the number of smaller elements following (k) (the “backward” inversion table). Both tables satisfy (0\le b_k\le n-k) and (0\le c_k\le k-1), and (\sum b_k = \sum c_k = B), the total number of inversions.

Basic Properties

Lemma 1. A forward pass decreases every positive (b_k) by exactly 1 and leaves all zero (b_k) unchanged. A backward pass decreases every positive (c_k) by exactly 1 and leaves all zero (c_k) unchanged.

Proof. The forward pass is exactly one pass of the ordinary bubble sort (Algorithm B). Theorem I of Section 5.2.2 proves the statement for (b_k). The backward pass is symmetric: if we reverse the array and replace each key (k) by (n+1-k), a backward pass becomes a forward pass on the transformed permutation. The inversion table of the transformed permutation is precisely (c_k), so the same reasoning applies. ∎

Corollary. The total number of exchanges performed during the whole sorting process equals (B), the total number of inversions of the initial permutation. (Each exchange reduces (B) by 1, and the algorithm stops when (B=0).)

Lemma 2. Let (L) and (R) be the bounds at the start of a pass. The number of comparisons in that pass is (R-L). If the pass makes at least one exchange, the new bound ((R) after a forward pass, (L) after a backward pass) equals the index (t) of the last exchange.

Proof. Directly from the algorithm. ∎

Distribution of the Number of Passes

Let (F) be the number of exchange‑making forward passes and (B) the number of exchange‑making backward passes. The algorithm terminates after a final pass that makes no exchanges, so the total number of passes is

[ A = F + B + 1. ]

Because the algorithm always starts with a forward pass, the last exchange‑making pass is forward iff (F = B+1), and backward iff (F = B).

The effect of a sequence of passes on the inversion tables can be tracked. After (f) forward passes and (b) backward passes the remaining “disorder” is described by modified tables (b_k^{(f,b)}) and (c_k^{(f,b)}). Although a forward pass changes (c_k) and a backward pass changes (b_k) in a somewhat complicated way, the condition that the permutation becomes sorted after exactly (f) forward and (b) backward passes is equivalent to a set of inequalities on the initial tables (b_k, c_k). By analysing the dynamics one obtains the following characterisation (see Exercises 5.4.8-9 for a detailed derivation):

The algorithm terminates after an odd number (A = 2m+1) of passes (the final pass is forward) iff
after (m) forward and (m) backward passes the array is sorted, but it is not yet sorted after (m) forward and (m-1) backward passes.
This is equivalent to:
[ \max_k b_k \le m,\qquad \max_k c_k \le m, ] and at least one of the two maxima equals (m) (otherwise we would have stopped earlier).
The algorithm terminates after an even number (A = 2m) of passes (the final pass is backward) iff
after (m) forward and (m-1) backward passes the array is sorted, but not after (m-1) forward and (m-1) backward passes.
This is equivalent to:
[ \max_k b_k \le m,\qquad \max_k c_k \le m-1, ] with (\max_k b_k = m) (because the last exchange‑making pass was forward).

These conditions can be expressed purely in terms of the initial inversion tables. Consequently, the number of permutations requiring exactly (A) passes is the number of pairs of inversion tables ((b,c)) satisfying the corresponding inequalities. This yields explicit formulas for the distribution, analogous to Eq. (6) for ordinary bubble sort. For example, the probability that (A \le 2m+1) is the fraction of inversion tables with (b_k \le m) and (c_k \le m) for all (k); the probability that (A \le 2m) is the fraction with (b_k \le m) and (c_k \le m-1) for all (k).

Average Number of Passes

Summing the distribution by parts gives the average number of passes

[ A_{\rm ave} = \sum_{m\ge 0} \Pr(A > m). ]

Using the characterisation above, this becomes a sum over the probabilities that the initial tables violate the bounds. The exact expression is

[ A_{\rm ave} = n + 1 - \frac{1}{n!}\sum_{k} #{\text{inversion tables with } b_k, c_k \text{ satisfying certain bounds}}. ]

The asymptotic evaluation of this sum is carried out in Exercise 5.4.9. The result is

[ A_{\rm ave} = n - \sqrt{\frac{\pi n}{2}} + O(1). ]

Thus the leading term is the same as for ordinary bubble sort (Eq. (7)), but the constant term differs.

Average Number of Comparisons

The number of comparisons (C) is the sum of (R-L) over all passes. Using the bounds (L) and (R) after each pass, one can express (C) in terms of the initial inversion tables. Let (c_j^{(f)}) be the value of (R-L) at the beginning of the (j)-th forward pass, and (c_j^{(b)}) the value at the beginning of the (j)-th backward pass. Then

[ C = \sum_{j=1}^{F} c_j^{(f)} + \sum_{j=1}^{B} c_j^{(b)}. ]

Analogous to Eq. (5), each (c_j^{(f)}) is the maximum over certain indices of (b_k + k) minus a shift, and each (c_j^{(b)}) is a similar maximum over (c_k). Averaging over all permutations leads to a double sum similar to Eq. (9):

[ C_{\rm ave} = \binom{n+1}{2} - \frac{1}{n!}\sum_{\text{certain ranges}} f_j(k), ]

where (f_j(k)) counts inversion tables satisfying appropriate inequalities. Exercise 5.4.9 evaluates this sum asymptotically, yielding

[ C_{\rm ave} = \frac{1}{2}n^2 - \frac{1}{2}n\ln n + O(n). ]

(For comparison, ordinary bubble sort has (C_{\rm ave} = \frac{1}{2}n^2 - \frac{1}{2}n\ln n + O(n)) with a different constant in the (O(n)) term; see Eq. (12).)

Partial Argument - Recurrence for the Distribution

A more structural approach uses the position of the largest element (n). During the first forward pass, (n) bubbles all the way to the right bound and becomes fixed at position (R). The remaining (n-1) elements are then sorted by a process that starts with a backward pass. This gives a recurrence for the number (N_n(A)) of permutations of length (n) requiring exactly (A) passes:

[ N_n(2m+1) = \sum_{k=1}^{n} N_{k-1}^{(b)}(m) \cdot N_{n-k}^{(f)}(m), \qquad N_n(2m) = \sum_{k=1}^{n} N_{k-1}^{(b)}(m-1) \cdot N_{n-k}^{(f)}(m), ]

where (N_{k}^{(f)}(m)) counts permutations of (k) elements that can be sorted in at most (m) forward passes (starting with a forward pass), and (N_{k}^{(b)}(m)) counts those that can be sorted in at most (m) backward passes (starting with a backward pass). These auxiliary numbers satisfy similar recurrences, leading to a generating function that is analysed in Exercises 5.4.8-9.

Status

The exact distribution of passes and comparisons is given by the recurrences above; no elementary closed form is known.
The asymptotic formulas for the averages are established in Exercises 5.4.8-9: [ A_{\rm ave} = n - \sqrt{\frac{\pi n}{2}} + O(1),\qquad C_{\rm ave} = \frac{1}{2}n^2 - \frac{1}{2}n\ln n + O(n). ]
The variance and higher moments of the number of passes, as well as the exact constant terms in the asymptotics, remain open research problems (hence the M48 rating).
The analysis of the cocktail‑shaker sort is more intricate than that of the ordinary bubble sort because the two inversion tables interact during the alternating passes; the complete solution requires the machinery developed in Section 5.4.8-9. ∎