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

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

Last updated