TAOCP 5.2: Internal Sorting

Section 5.2 exercises: 5/5 solved.

5 items

Section 5.2. Internal Sorting

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

#	Rating	Status	Time
1	[**]	solved	10m42s
2	[**]	solved	10m13s
3	[**]	verified	5m44s
4	[**]	solved	10m07s
5	[**]	solved	7m43s

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.