15 Chapter 15 Solutions¶
Solution to Challenge 1¶
If you start with the following list:
[4, 2, 5, 1, 3]
Here are the steps a bubble sort would take:
[2, 4, 5, 1, 3] // 4-2 swapped
[2, 4, 5, 1, 3] // 4-5 not swapped
[2, 4, 1, 5, 3] // 5-1 swapped
[2, 4, 1, 3, 5] // 5-3 swapped
[2, 4, 1, 3, 5] // 2-4 not swapped
[2, 1, 4, 3, 5] // 4-1 swapped
[2, 1, 3, 4, 5] // 4-3 swapped
[1, 2, 3, 4, 5] // 2-1 swapped
[1, 2, 3, 4, 5] // 2-3 not swapped
[1, 2, 3, 4, 5] // 1-2 not swapped
Bubble sort needed the full O(n²) traversal to finish the sort. It made ten comparisons and six swaps.
Solution to Challenge 2¶
Given the following list:
[4, 2, 5, 1, 3]
These are the steps a selection sort would take:
[4, 2, 5, 1, 3] // start, lowest: 4
[4, 2, 5, 1, 3] // compare 2-4, lowest: 2
[4, 2, 5, 1, 3] // compare 5-2, lowest: 2
[4, 2, 5, 1, 3] // compare 1-2, lowest: 1
[4, 2, 5, 1, 3] // compare 3-1, lowest: 1
// swap 4-1, reset lowest: 2
[1, 2, 5, 4, 3] // compare 5-2, lowest: 2
[1, 2, 5, 4, 3] // compare 4-2, lowest: 2
[1, 2, 5, 4, 3] // compare 3-2, lowest: 2
// no swap needed, reset lowest: 5
[1, 2, 5, 4, 3] // compare 4-5, lowest: 4
[1, 2, 5, 4, 3] // compare 3-4, lowest: 3
// swap 5-3, reset lowest: 4
[1, 2, 3, 4, 5] // compare 5-4, lowest: 4
// no swap needed
This solution also needed the full O(n²) traversal with its ten comparisons. However, selection sort completed the task with only two swaps.
Solution to Challenge 3¶
Using the following list:
[4, 2, 5, 1, 3]
An insertion sort would perform the steps below:
[2, 4, 5, 1, 3] // 4-2 swapped
[2, 4, 5, 1, 3] // 4-5 not swapped
[2, 4, 1, 5, 3] // 5-1 swapped
[2, 1, 4, 5, 3] // 4-1 swapped
[1, 2, 4, 5, 3] // 2-1 swapped
[1, 2, 4, 3, 5] // 5-3 swapped
[1, 2, 3, 4, 5] // 4-3 swapped
[1, 2, 3, 4, 5] // 2-3 not swapped
Insertion sort was able to do a little better than O(n²) since on the second and fourth passes it found some presorted elements. Those steps are marked with “not swapped” in the comments above. Overall this solution required eight comparisons and six swaps.
Solution to Challenge 4¶
Each of the sort algorithms below is working on the following sorted collection:
[1, 2, 3, 4, 5]
Bubble Sort¶
Here are the steps bubble sort would take:
[1, 2, 3, 4, 5] // 1-2 not swapped
[1, 2, 3, 4, 5] // 2-3 not swapped
[1, 2, 3, 4, 5] // 3-4 not swapped
[1, 2, 3, 4, 5] // 4-5 not swapped
Since bubble sort completed an entire pass without needing to swap any elements, it could exit early after only one pass. This is O(n) time complexity. However, if you simply moved the 1 to the end of the list, bubble sort would suddenly become O(n²) again.
Selection Sort¶
These are the steps selection sort would take:
[1, 2, 3, 4, 5] // compare 2-1, lowest: 1
[1, 2, 3, 4, 5] // compare 3-1, lowest: 1
[1, 2, 3, 4, 5] // compare 4-1, lowest: 1
[1, 2, 3, 4, 5] // compare 5-1, lowest: 1
// no swap needed, reset lowest: 2
[1, 2, 3, 4, 5] // compare 3-2, lowest: 2
[1, 2, 3, 4, 5] // compare 4-2, lowest: 2
[1, 2, 3, 4, 5] // compare 5-2, lowest: 2
// no swap needed, reset lowest: 3
[1, 2, 3, 4, 5] // compare 4-3, lowest: 3
[1, 2, 3, 4, 5] // compare 5-3, lowest: 3
// no swap needed, reset lowest: 4
[1, 2, 3, 4, 5] // compare 5-4, lowest: 4
// no swap needed
Even with a fully sorted list, selection sort is still O(n²).
Insertion Sort¶
And these are the steps insertion sort would take:
[1, 2, 3, 4, 5] // 1-2 not swapped
[1, 2, 3, 4, 5] // 2-3 not swapped
[1, 2, 3, 4, 5] // 3-4 not swapped
[1, 2, 3, 4, 5] // 4-5 not swapped
Like bubble sort, insertion sort is able to determine that the list is sorted with a single pass, giving it a time complexity of O(n). However, unlike bubble sort, moving 1 to the end of the list wouldn’t cause insertion sort to jump all the way back up to O(n²).