TAOCP 5.2.2: Sorting by Exchanging

Section 5.2.2 exercises: 7/7 solved.

7 items

Section 5.2.2. Sorting by Exchanging

Exercises from TAOCP Volume 3 Section 5.2.2: 7/7 solved.

#	Rating	Status	Time
1	[**]	verified	1m26s
2	[**]	verified	1m52s
3	[**]	verified	1m42s
4	[**]	verified	6m17s
5	[**]	solved	7m26s
6	[**]	solved	3m08s
7	[**]	solved	2m53s

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2.2: Sorting by Exchanging ›

TAOCP 5.2.2 Exercise 1

Let $x = a_i$ and $y = a_j$ with $i < j$ and $x > y$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2.2: Sorting by Exchanging ›

TAOCP 5.2.2 Exercise 2

(a) The permutation $376981452$ has the disjoint cycle decomposition (1\,3\,6\,4\,9\,2\,7)(5\,8).

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2.2: Sorting by Exchanging ›

TAOCP 5.2.2 Exercise 3

Yes, Algorithm B is a stable sorting algorithm.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2.2: Sorting by Exchanging ›

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...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2.2: Sorting by Exchanging ›

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$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2.2: Sorting by Exchanging ›

TAOCP 5.2.2 Exercise 6

Algorithm M (as used in Section 5.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.2.2: Sorting by Exchanging ›

TAOCP 5.2.2 Exercise 7

Batcher’s merge-exchange method is not stable.

TAOCP 5.2.2: Sorting by Exchanging

Section 5.2.2. Sorting by Exchanging

TAOCP 5.2.2 Exercise 1

TAOCP 5.2.2 Exercise 2

TAOCP 5.2.2 Exercise 3

TAOCP 5.2.2 Exercise 4

TAOCP 5.2.2 Exercise 5

TAOCP 5.2.2 Exercise 6

TAOCP 5.2.2 Exercise 7