29.6 Exercises

Factual

  1. 1.
    How many inversions are there in the array [10, 100, 60, 40, 50]?
  2. 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. 1.
    Draw the process of heapsort on the array [5, 9, 2], starting with the heapified array and removing the maximum each time.
  2. 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. 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.