Chapter 3: Simple Sorting

Question 1

Bubble sort

Answer 1

Algorithm: Move left to right doing pairwise compare / swaps. After each iteration, one less item needs to be compared (e.g. last index to check is always decremented)
Complexity: worst-case => n2; average => n2
Invariant: Objects to the right of the outer index are always sorted and are the largest items

Question 2

Selection sort

Answer 2

Algorithm: starting from left side of array, does a sequential scan at each index for the next lowest item in the remainder of the array
Complexity: worst-case => n**2 comparisons
Invariant: Objects on the left are always sorted

Question 3

Insertion sort

Answer 3

Algorithm: does a single scan through array but at each input must find the objects rightful place and shift all those items greater to the right.
Complexity: worst-case => n**2 comparisons and swaps