TAOCP 5.2.2 Exercise 22

We first prove the recurrence for \(A_N(z)\).

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.2.2: Sorting by Exchanging

Exercise 22. [M25] Let $p_{kN}$ be the probability that the quantity $A$ in (16) will equal $k$, when Algorithm Q is applied to a random permutation of ${1, 2, \ldots, N}$, and let $A_N(z) = \sum_k p_{kN} z^k$ be the corresponding generating function. Prove that $A_N(z) = 1$ for $N \le M$, and $A_N(z) = \frac{1}{N} \sum_{1 \le j \le N} A_{j-1}(z) A_{N-j}(z)$ for $N > M$. Find probability distributions $B_N(z)$, $C_N(z)$, $D_N(z)$, $E_N(z)$, $S_N(z)$.

Verified: no
Solve time: 12m57s

Solution

We first prove the recurrence for (A_N(z)). Let (A) be the quantity defined in Eq. (16). For (N \le M), Algorithm Q does not enter the partitioning phase; it sorts the file directly by straight insertion. According to the definition of (A), this means (A = 0) with probability 1, so (A_N(z) = 1).

For (N > M), the algorithm chooses a pivot uniformly at random from ({1,\dots,N}); let the pivot be (j). The file is partitioned into a left subfile of size (j-1) and a right subfile of size (N-j). The algorithm then recursively sorts these two subfiles. The quantity (A) for the whole file is the sum of the quantities (A) for the left and right subfiles (the current partitioning step does not contribute to (A)). Because the original permutation is random, the left and right subfiles are independent random permutations of their elements. Hence the probability generating function of the sum is the product of the generating functions, and averaging over the pivot position yields [ A_N(z) = \frac{1}{N} \sum_{j=1}^N A_{j-1}(z) A_{N-j}(z). ]

Now we find the probability distributions for the remaining quantities.

Let (B) be the number of comparisons, (C) the number of exchanges, (D) the number of pushes onto the stack, (E) the number of pops from the stack, and (S) the maximum stack size during the execution of Algorithm Q on a random permutation of size (N).

For (N \le M), the algorithm sorts the subfile by straight insertion (Algorithm 5.2.1S). The distributions of (B) and (C) are given by the generating functions (B_N^0(z)) and (C_N^0(z)) derived from the analysis of straight insertion on a random permutation of size (N). No stack operations occur, so (D_N(z) = E_N(z) = 1), and the maximum stack size is (0), so (S_N(z) = 1).

For (N > M), the algorithm performs one partitioning phase. Let (c(N,j)) and (e(N,j)) denote the number of comparisons and exchanges, respectively, when a file of size (N) is partitioned with pivot (j) (these are given by Eq. (17)). After partitioning, the larger subfile is pushed onto the stack and the smaller subfile is processed recursively; finally the larger subfile is popped and processed.

  • Comparisons: The total number is (c(N,J) + B_{J-1} + B_{N-J}). Hence [ B_N(z) = \frac{1}{N} \sum_{j=1}^N z^{c(N,j)} B_{j-1}(z) B_{N-j}(z). ]
  • Exchanges: Similarly, [ C_N(z) = \frac{1}{N} \sum_{j=1}^N z^{e(N,j)} C_{j-1}(z) C_{N-j}(z). ]
  • Pushes: One push is performed, and both subfiles are fully processed, so the total number of pushes is (1 + D_{J-1} + D_{N-J}). Thus [ D_N(z) = \frac{z}{N} \sum_{j=1}^N D_{j-1}(z) D_{N-j}(z). ]
  • Pops: Each push is eventually popped, so (E_N = D_N). Hence [ E_N(z) = \frac{z}{N} \sum_{j=1}^N E_{j-1}(z) E_{N-j}(z). ]
  • Maximum stack size: Let (a = \min(j-1, N-j)) and (b = \max(j-1, N-j)). While processing the smaller subfile of size (a), the stack contains one extra entry (the larger subfile), so the maximum stack size during that phase is (S_a + 1). While processing the larger subfile of size (b), the stack size returns to its previous level, so the maximum is (S_b). The overall maximum is (\max(S_a + 1, S_b)). Therefore the generating function satisfies [ S_N(z) = \frac{1}{N} \sum_{j=1}^N \mathbb{E}\bigl[z^{\max(S_{j-1}+1, S_{N-j})}\bigr], ] where the expectation is over the independent random variables (S_{j-1}) and (S_{N-j}). Equivalently, the probability distribution can be computed from [ \Pr(S_N = k) = \frac{1}{N} \sum_{j=1}^N \Pr\bigl(\max(S_{j-1}+1, S_{N-j}) = k\bigr). ]

This completes the solution. ∎