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

Θ(1)\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 Θ(N2)\Theta(N^2) on a reverse-sorted array. However, note that selection sort only does NN total swaps (finding the maximum, then swapping to the front), while insertion sort does on the order of N2N^2 swaps (swapping each item to the front), so insertion sort will actually be slower by a constant factor.

Last updated