TAOCP 5.2.1: Sorting by Insertion
Section 5.2.1 exercises: 14/14 solved.
Section 5.2.1. Sorting by Insertion
Exercises from TAOCP Volume 3 Section 5.2.1: 14/14 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | solved | 13m25s | |
| 2 | [**] | verified | 1m15s | |
| 3 | [**] | solved | 9m01s | |
| 4 | [**] | verified | 16m17s | |
| 5 | [**] | solved | 32m26s | |
| 6 | [23] | medium | verified | 1m27s |
| 7 | [M20] | math-medium | verified | 14m42s |
| 8 | [10] | simple | solved | 4m47s |
| 9 | [20] | medium | solved | 3m37s |
| 10 | [22] | medium | verified | 1m29s |
| 11 | [M10] | math-simple | verified | 2m59s |
| 12 | [M20] | math-medium | verified | 2m46s |
| 13 | [M16] | math-medium | verified | 2m55s |
| 14 | [M28] | math-hard | solved | 4m47s |
TAOCP 5.2.1 Exercise 1
Yes.
TAOCP 5.2.1 Exercise 2
Let step S4 in Algorithm S be the comparison step that determines whether the current key $K$ should be inserted before $K_i$ or whether $K_i$ should be moved right.
TAOCP 5.2.1 Exercise 3
No.
TAOCP 5.2.1 Exercise 4
The running time of Program S is $9B+10N-3A-9.$ By the results stated in Section 5.
TAOCP 5.2.1 Exercise 5
**Exercise 5.
TAOCP 5.2.1 Exercise 6
Let $R_1,\dots,R_N$ be the records, and let their final order after two-way insertion be determined as in Table 2, where each new record is inserted either to the left end or the right end of the curr...
TAOCP 5.2.1 Exercise 7
Let $a_1 a_2 \dots a_n$ be a random permutation of ${1,2,\dots,n}$.
TAOCP 5.2.1 Exercise 8
A correct solution must address stability in the sense of TAOCP: records with equal keys must preserve their relative order after the entire Shellsort process.
TAOCP 5.2.1 Exercise 9
The flaw in the previous solution is that it never uses the data in Tables 3 and 4.
TAOCP 5.2.1 Exercise 10
In step D3, Program D performs three actions before any comparison outcome is known: it sets $i = j - h$, it loads $K = K_j$, and it loads $R = R_j$.
TAOCP 5.2.1 Exercise 11
Let \pi = (1,2,5,3,7,4,8,6,9,11,10,12).
TAOCP 5.2.1 Exercise 12
A 2-ordered permutation $a_1a_2\cdots a_n$ satisfies a_i<a_{i+2}\qquad (1\le i\le n-2).