TAOCP 5.2.2: Sorting by Exchanging
Section 5.2.2 exercises: 56/56 solved.
Section 5.2.2. Sorting by Exchanging
Exercises from TAOCP Volume 3 Section 5.2.2: 56/56 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M20] | math-medium | verified | 1m26s |
| 2 | ▶ [M23] | math-medium | verified | 1m52s |
| 3 | [10] | simple | verified | 1m42s |
| 4 | [M23] | math-medium | verified | 6m17s |
| 5 | [M25] | math-medium | solved | 7m26s |
| 6 | [M22] | math-medium | solved | 3m08s |
| 7 | [M28] | math-hard | solved | 2m53s |
| 8 | [M24] | math-medium | solved | 2m36s |
| 9 | [M48] | math-research | solved | 33m58s |
| 10 | [M26] | math-hard | solved | 1h29m |
| 11 | ▶ [M25] | math-medium | solved | 15m08s |
| 12 | [24] | medium | solved | 1h13m |
| 13 | [10] | simple | solved | 4m16s |
| 14 | [M21] | math-medium | solved | 14m20s |
| 15 | [M38] | math-project | solved | 32m53s |
| 16 | [HM42] | hm-project | solved | 25m39s |
| 17 | ▶ [20] | medium | solved | 1m23s |
| 18 | ▶ [20] | medium | solved | 6m31s |
| 19 | [15] | simple | solved | 38s |
| 20 | [M20] | math-medium | solved | 12m52s |
| 21 | [20] | medium | solved | 6m45s |
| 22 | [M25] | math-medium | solved | 12m57s |
| 23 | [M23] | math-medium | solved | 17m35s |
| 24 | [M21] | math-medium | solved | 44m16s |
| 25 | [M20] | math-medium | solved | 11m16s |
| 26 | ▶ [M24] | math-medium | solved | 14m35s |
| 27 | [M28] | math-hard | solved | 17m30s |
| 28 | [M26] | math-hard | solved | 6m56s |
| 29 | [HM40] | hm-project | solved | 25m35s |
| 30 | ▶ [25] | medium | solved | 30s |
| 31 | [20] | medium | solved | 22m14s |
| 32 | [M10] | math-simple | solved | 1h11m |
| 33 | ▶ [15] | simple | solved | 54s |
| 34 | [20] | medium | solved | 1m27s |
| 35 | [M23] | math-medium | solved | 50m30s |
| 36 | [M27] | math-hard | solved | 23m15s |
| 37 | [M28] | math-hard | solved | 3m08s |
| 38 | ▶ [M30] | math-hard | solved | 54m40s |
| 39 | [20] | medium | solved | 3m18s |
| 40 | [21] | medium | solved | 8m37s |
| 41 | ▶ [30] | hard | solved | 6m55s |
| 42 | [HM32] | hm-hard | solved | 1h45m |
| 43 | [HM21] | hm-medium | solved | 52s |
| 44 | [HM24] | hm-medium | solved | 12m24s |
| 45 | [HM20] | hm-medium | solved | 23m06s |
| 46 | [HM20] | hm-medium | solved | 12m49s |
| 47 | [HM21] | hm-medium | solved | 4m07s |
| 48 | [HM24] | hm-medium | solved | 15m06s |
| 49 | [HM44] | hm-project | solved | 13m24s |
| 50 | [HM24] | hm-medium | solved | 51m56s |
| 51 | ▶ [HM28] | hm-hard | solved | 7m01s |
| 52 | [HM35] | hm-hard | solved | 1h37m |
| 53 | [HM42] | hm-project | solved | 21m11s |
| 54 | [HM24] | hm-medium | solved | 23m27s |
| 55 | ▶ [22] | medium | solved | 9m33s |
| 56 | [M19] | math-medium | solved | 25m52s |
TAOCP 5.2.2 Exercise 1
Let $x = a_i$ and $y = a_j$ with $i < j$ and $x > y$.
TAOCP 5.2.2 Exercise 2
(a) The permutation $376981452$ has the disjoint cycle decomposition (1\,3\,6\,4\,9\,2\,7)(5\,8).
TAOCP 5.2.2 Exercise 3
Yes, Algorithm B is a stable sorting algorithm.
TAOCP 5.2.2 Exercise 4
The flaw in the previous solution is the attempt to characterize the event using the original suffix $R_2,\dots,R_n$ without tracking how a bubble sort pass changes the array after the first compariso...
TAOCP 5.2.2 Exercise 5
Let $b_1 b_2 \dots b_n$ be the inversion table of the permutation $a_1 a_2 \dots a_n$.
TAOCP 5.2.2 Exercise 6
Algorithm M (as used in Section 5.
TAOCP 5.2.2 Exercise 7
Batcher’s merge-exchange method is not stable.
TAOCP 5.2.2 Exercise 8
We derive the formula for \(f_j(k)\) from its definition.
TAOCP 5.2.2 Exercise 9
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\).
TAOCP 5.2.2 Exercise 10
We need to solve Exercise 10 from Section 5.
TAOCP 5.2.2 Exercise 11
Batcher's merge-exchange sort for \(n = 16\) is an odd-even merge sort.
TAOCP 5.2.2 Exercise 12
The algorithm intended by the exercise (binary computer with `AND` and `SRB`) is the radix exchange sort (Algorithm R in the text).
TAOCP 5.2.2 Exercise 13
Yes, Batcher's merge exchange sort is stable.
TAOCP 5.2.2 Exercise 14
In Batcher's merge exchange sort (Algorithm M), the number of key comparisons \(c(N)\) for \(N = 2^t\) satisfies a simple recurrence.
TAOCP 5.2.2 Exercise 15
We analyze the number of comparisons \(c(N)\) in Batcher's merge exchange sort (Algorithm M).
TAOCP 5.2.2 Exercise 16
We consider Batcher's merge‑exchange sort (Algorithm M in the text) applied to a random permutation of \(N = 2^t\) distinct keys.
TAOCP 5.2.2 Exercise 17
In Algorithm Q (Quicksort), the sentinel values \(K_0 = -\infty\) and \(K_{N+1} = +\infty\) (postulated in equation (12)) are used in the two scanning loops of the partitioning phase.
TAOCP 5.2.2 Exercise 18
Algorithm Q (Hoare’s quicksort) from Section 5.
TAOCP 5.2.2 Exercise 19
Yes, Algorithm Q would still work properly if a queue (FIFO) were used instead of a stack (LIFO).
TAOCP 5.2.2 Exercise 20
In Algorithm Q (Quicksort), a stack is used to keep track of subfiles that remain to be sorted.
TAOCP 5.2.2 Exercise 21
We first recall the first partitioning phase of Algorithm Q (quicksort) as described in the text.
TAOCP 5.2.2 Exercise 22
We first prove the recurrence for \(A_N(z)\).
TAOCP 5.2.2 Exercise 23
We are given that \(A_N, B_N, C_N, D_N, S_N\) are the average values of the quantities defined in (16) when Algorithm Q (quicksort with cutoff \(M\)) is applied to a random permutation of \(\{1,2,\ldo...
TAOCP 5.2.2 Exercise 24
We consider the modification of Algorithm Q (Hoare's quicksort) where the partitioning phase avoids all key comparisons when the scanning indices satisfy \(i \ge j\).
TAOCP 5.2.2 Exercise 25
We consider Program Q (quicksort) as described in Section 5.
TAOCP 5.2.2 Exercise 26
The worst-case running time of Program Q (Quicksort with a cutoff to straight insertion for subfiles of size \(\le M\)) is achieved by an input that forces the maximum number of partitioning stages wh...
TAOCP 5.2.2 Exercise 27
Algorithm Q (Quicksort) is the partition‑exchange method described in Section 5.
TAOCP 5.2.2 Exercise 28
We analyze Singleton's modification of Algorithm Q (Quicksort), where the pivot \(s\) is chosen as the median of the three elements \(K_1, K_{\lfloor(N+1)/2\rfloor}, K_N\).
TAOCP 5.2.2 Exercise 29
Let \(C_N\) denote the average number of key comparisons performed by Singleton’s median‑of‑three quicksort when sorting \(N\) distinct elements, **excluding** the three comparisons used to find the m...
TAOCP 5.2.2 Exercise 30
When multiword keys are sorted lexicographically, the standard quicksort (Algorithm Q) wastes time by repeatedly comparing equal leading words as the subfiles become smaller.
TAOCP 5.2.2 Exercise 31
We adapt Algorithm Q (quicksort) to find the $m$th smallest element ($1 \le m \le n$) of a file of $n$ distinct elements.
TAOCP 5.2.2 Exercise 32
We need to solve Exercise 32 from TAOCP Volume 3, Section 5.
TAOCP 5.2.2 Exercise 33
We are given a table $A[1 \ldots N]$ of numbers.
TAOCP 5.2.2 Exercise 34
In Algorithm R (Radix exchange sort), steps R3 and R4 (the bit‑inspection loops) repeatedly scan from the left for an element whose current bit is 1 and from the right for an element whose current bit...
TAOCP 5.2.2 Exercise 35
We analyze the radix exchange sorting algorithm (Program R) for the “case (i) input” described in the text: the file contains \(N\) records whose keys are infinite sequences of independent random bits...
TAOCP 5.2.2 Exercise 36
The binomial transform of a sequence \(\langle a_n\rangle = a_0, a_1, a_2,\ldots\) is defined by \[ \hat{a}_n = \sum_{k=0}^n \binom{n}{k}(-1)^k a_k \qquad (n\ge 0).
TAOCP 5.2.2 Exercise 37
Let \(\langle a_n \rangle = a_0, a_1, a_2, \ldots\) be a sequence.
TAOCP 5.2.2 Exercise 38
Let the quantities \(A,B,C,G,K,L,R,S,X\) be defined as in the analysis of radix exchange (equation (29)).
TAOCP 5.2.2 Exercise 39
**Quicksort.
TAOCP 5.2.2 Exercise 40
Algorithm R (radix exchange sort) sorts a file of \(N\) records \(R_1,\dots,R_N\) with keys \(K_1,\dots,K_N\) by examining the bits of the keys from the most significant to the least significant.
TAOCP 5.2.2 Exercise 41
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\).
TAOCP 5.2.2 Exercise 42
We need to solve Exercise 42 from Volume 3, Section 5.
TAOCP 5.2.2 Exercise 43
We prove the identity \[ \int_0^1 \frac{e^{-y}-1}{y}\,dy \;+\; \int_1^\infty \frac{e^{-y}}{y}\,dy \;=\; -\gamma, \] where \(\gamma\) is the Euler-Mascheroni constant.
TAOCP 5.2.2 Exercise 44
We derive the asymptotic formula for the average number of comparisons in the bubble sort (Equation (37) in the text).
TAOCP 5.2.2 Exercise 45
In the text, equation (43) is the integral representation \frac{1}{n!
TAOCP 5.2.2 Exercise 46
We evaluate the integral \[ I = \frac{1}{2\pi i} \int_{s-i\infty}^{s+i\infty} \frac{\Gamma(z)\, n^{-z}}{2^{z-1} - 1} \, dz, \] where \(s\) is a positive integer.
TAOCP 5.2.2 Exercise 47
We need to prove that the function \[ S(n) = \sum_{j=1}^{\infty} \frac{n}{2^j} e^{-n/2^j} \] is bounded for all \(n > 0\).
TAOCP 5.2.2 Exercise 48
In Exercise 38, the quantity \(V_n\) is defined as \[ V_n = \frac{1}{n!
TAOCP 5.2.2 Exercise 49
In the analysis of bubble sort (Algorithm B) the average number of comparisons is \[ C_{\text{ave}} = \binom{n+1}{2} - U_n, \] where the quantity \(U_n\) is defined by \[
TAOCP 5.2.2 Exercise 50
We need to find the asymptotic value of U_{mn} = sum_{k >= 2} C(n,k) (-1)^k / (m^{k-1} - 1) for fixed m > 1 as n -> infinity.
TAOCP 5.2.2 Exercise 51
The quantity $r_k(m)$ is defined in equation (35) of the text as the sum of inverse powers \[ r_k(m) = \sum_{j=1}^{m} j^{-k} \qquad (k \ge 1), \] and the text derives its asymptotic expansion as $m \t...
TAOCP 5.2.2 Exercise 52
Let \[ S_n=\sum_{t\ge 1}\binom{2n}{n+t}d(t),\qquad C_n=\binom{2n}{n}, \qquad R_n=\frac{S_n}{C_n}=\sum_{k=1}^{n}\frac{\binom{2n}{n+k}}{C_n}\,d(k).
TAOCP 5.2.2 Exercise 53
Radix exchange sort (Algorithm R in Section 5.
TAOCP 5.2.2 Exercise 54
We are given the contour integral representation U_n = (-1)^n \frac{n!