29.6 Exercises

Factual

1. How many inversions are there in the array [10, 100, 60, 40, 50]?

2. What is the space complexity of selection sort?

Problem 1

5; the violations are 100 > 60, 100 > 40, 100 > 50, 60 > 40, and 60 > 50.

Problem 2

$\Theta(1)$. All swaps in selection sort happen in-place.

Procedural

1. Draw the process of heapsort on the array [5, 9, 2], starting with the heapified array and removing the maximum each time.

2. If we are insertion sorting [5, 6, 7, 1, 8, 9, 2], how many total swaps will occur?

Problem 1

After heapification: [9, 5, 2]. We sink in reverse level order, which means that we swap 5 with 9.

Then, the algorithm proceeds by popping off 9 ([5, 2 | 9]), then 5 ([2 | 5, 9]), then 2 ([2, 5, 9]).

Problem 2

8; simply count the number of inversions (5 > 1, 5 > 2, 6 > 1, 6 > 2, 7 > 1, 7 > 2, 8 > 2, 9 > 2).

Metacognitive

1. Which sort do you expect to run more quickly on a reversed array, selection sort or insertion sort?

Problem 1

Asymptotically, both selection and insertion sort run in $\Theta(N^2)$ on a reverse-sorted array. However, note that selection sort only does $N$ total swaps (finding the maximum, then swapping to the front), while insertion sort does on the order of $N^2$ swaps (swapping each item to the front), so insertion sort will actually be slower by a constant factor.