> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/29.-basic-sorts/29.6-exercises.md).

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

<details>

<summary>Problem 1</summary>

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

</details>

<details>

<summary>Problem 2</summary>

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

</details>

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

<details>

<summary>Problem 1</summary>

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]`).

</details>

<details>

<summary>Problem 2</summary>

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

</details>

## Metacognitive

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

<details>

<summary>Problem 1</summary>

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.

</details>