TAOCP 5.2.3: Sorting by Selection
Section 5.2.3 exercises: 15/15 solved.
Section 5.2.3. Sorting by Selection
Exercises from TAOCP Volume 3 Section 5.2.3: 15/15 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | verified | 1m16s | |
| 2 | [**] | verified | 1m27s | |
| 3 | [**] | solved | 7m38s | |
| 4 | [**] | verified | 2m56s | |
| 5 | [**] | solved | 6m05s | |
| 6 | [**] | verified | 3m39s | |
| 7 | [**] | verified | 1m42s | |
| 8 | [**] | verified | 4m45s | |
| 9 | [**] | verified | 2m26s | |
| 10 | [20] | medium | verified | 2m10s |
| 11 | [10] | simple | verified | 2m05s |
| 12 | [M22] | math-medium | verified | 1m28s |
| 13 | [20] | medium | verified | 5m53s |
| 14 | [20] | medium | verified | 3m52s |
| 15 | [21] | medium | verified | 8m12s |
TAOCP 5.2.3 Exercise 1
For a fixed value of $j$, step S2 selects the maximum of the keys $K_1,\ldots,K_j$.
TAOCP 5.2.3 Exercise 2
For the input $N,N-1,\ldots,2,1$, the sequence $K_1, K_2, \ldots, K_j$ is strictly decreasing for every $j \ge 2$.
TAOCP 5.2.3 Exercise 3
The previous solution failed because it used unsupported structural claims about cycles and an undefined “charging” argument.
TAOCP 5.2.3 Exercise 4
Let $R_j$ be the number of right-to-left maxima among $K_1,\dots,K_j$.
TAOCP 5.2.3 Exercise 5
The previous solution correctly implemented a left-to-right maximum search, but it never established the _inter-iteration structure_ that makes the modification useful.
TAOCP 5.2.3 Exercise 6
We analyze the algorithm of Exercise 5.
TAOCP 5.2.3 Exercise 7
After 14 outputs, all but two elements have been replaced by $-\infty$ in the tournament structure of Fig.
TAOCP 5.2.3 Exercise 8
**Corrected Solution: Exercise 5.
TAOCP 5.2.3 Exercise 9
Let the file contain $2^n$ elements and consider the bottom-up method of Fig.
TAOCP 5.2.3 Exercise 10
Let the standard heapsort “sift-down” step be denoted by the variables of Algorithm H, where a key at position $k$ is moved downward by repeatedly comparing it with its children at $2k$ and $2k+1$, an...
TAOCP 5.2.3 Exercise 11
Let elements arrive in a sequence at times $t = 1,2,\ldots$.
TAOCP 5.2.3 Exercise 12
Let $r$ denote the current odd integer under consideration and let $H$ be a priority queue keyed by the first unprocessed odd composite associated with each prime.
TAOCP 5.2.3 Exercise 13
**Exercise 5.
TAOCP 5.2.3 Exercise 14
Exercise 16 describes the standard heap insertion operation: append the new key at the end of the heap and repeatedly interchange it with its parent until the heap property is restored.