15.
Chapter 15 Solutions
Written by Jonathan Sande & Kelvin Lau
Heads up... You’re accessing parts of this content for free, with some sections shown as
text.
Heads up... You’re accessing parts of this content for free, with some sections shown as
text.Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
Unlock now
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]
[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
Solution to Challenge 3
Using the following list:
[4, 2, 5, 1, 3]
[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
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
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
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