TAOCP 5.2: Internal Sorting

Section 5.2 exercises: 13/13 solved.

13 items

Section 5.2. Internal Sorting

Exercises from TAOCP Volume 3 Section 5.2: 13/13 solved.

#	Rating	Category	Status	Time
1	[15]	simple	solved	10m42s
2	[21]	medium	solved	10m13s
3	▶ [21]	medium	verified	5m44s
4	[16]	medium	solved	10m07s
5	[22]	medium	solved	7m43s
6	[18]	medium	verified	8m10s
7	[13]	simple	verified	5m28s
8	[18]	medium	verified	10m36s
9	[29]	hard	solved	15m18s
10	[25]	medium	solved	7m23s
11	[M27]	math-hard	solved	1h33m
12	▶ [25]	medium	verified	24m25s
13	▶ [27]	hard	solved	11m17s

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2: Internal Sorting ›

TAOCP 5.2 Exercise 1

Algorithm C still works if $i$ varies from $2$ up to $N$ in step C2 instead of from $N$ down to $2$, because the comparisons made in step C4 depend only on the relative ordering of $K_i$ and $K_j$, no...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2: Internal Sorting ›

TAOCP 5.2 Exercise 2

For each pair $(j,i)$ with $j<i$, step C4 increases exactly one of `COUNT[j]` or `COUNT[i]`.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2: Internal Sorting ›

TAOCP 5.2 Exercise 3

No.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2: Internal Sorting ›

TAOCP 5.2 Exercise 4

After Program C has terminated, the value $\mathrm{COUNT}[i]+1$ is the final position of record $R_i$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2: Internal Sorting ›

TAOCP 5.2 Exercise 5

The changes preserve correctness.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2: Internal Sorting ›

TAOCP 5.2 Exercise 6

We simulate Algorithm D (Distribution counting) on the 16 records: | $j$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |------|---|---|---|---|---|---|---|---|---|----|---...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2: Internal Sorting ›

TAOCP 5.2 Exercise 7

Algorithm D is stable.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2: Internal Sorting ›

TAOCP 5.2 Exercise 8

The modified algorithm (with step D5 looping $j = 1, 2, \ldots, N$) **still produces a correctly sorted array** (all keys in non‑decreasing order), but **it is no longer stable** - the relative orde...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2: Internal Sorting ›

TAOCP 5.2 Exercise 9

We assume the following memory layout and conventions, analogous to Program C: - `INPUT` is the base address of the input records; record $R_j$ is stored in `INPUT+j` for $1 \le j \le N$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2: Internal Sorting ›

TAOCP 5.2 Exercise 10

We are given an array of records $R[1\ldots N]$ and a permutation $p(1)\ldots p(N)$ of $\{1,\ldots,N\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2: Internal Sorting ›

TAOCP 5.2 Exercise 11

After Algorithm C, the `COUNT` array satisfies `COUNT[j] =` number of keys strictly less than `K_j`; hence the final position of record `R_j` is `COUNT[j] + 1`.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2: Internal Sorting ›

TAOCP 5.2 Exercise 12

After the list sort (Fig.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2: Internal Sorting ›

TAOCP 5.2 Exercise 13

We are given $N$ records $R_1,\dots,R_N$ with integer keys $K_1,\dots,K_N$ satisfying $u \le K_j \le v$.