# 29.6 Exercises

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

? - 2.What is the space complexity of selection sort?

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

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

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.Last modified 11mo ago