Summary
Efficiency for all three is $O(n^2)$, hence "quadratic sorting algorithms".
| Sort | Elevator pitch! |
|---|---|
| Bubble | compare adjacent values, swap if out of order |
| Selection | find next smallest, swap into final position |
| Insertion | consider each element, move to left as far as it needs to go |
Exercise Suppose we have the following array contents after the third pass of the outer loop of some quadratic sorting algorithm meant to put the array in ascending order:
$$ 3, 5, 7, 8, 2, 9, 4, 10, 15, 20 $$
Which sorting algorithm could be operating on this array?
A) bubble (up) sort
B) (min) selection sort
C) insertion sort
D) none of these
Solution
The answer is (A) & (C).
The last three elements of the array are the three largest elements in order so it could be bubble sort operating on it.
The first three elements are not the three smallest elements so it could not be selection sort.
The first three elements are in order so it could be insertions sort. (If you implement the insertion sort as to start from the second element, it can still be argued the first four elements are in sorted order).
Resources
There are great demos on the VisuAlgo website. In particular to show sorting algorithms:
- Go to https://visualgo.net/en/sorting
- Press Esc to get rid of the popup (if you login then it will not show up)
- Choose the type of sort in top bar (Bubble, Sel, Ins)
- On the bottom left, press create and add the data set (here you can choose if you want it in random, sorted or nearly sorted order)
- In the bottom left corner, you can adjust the speed from by moving the bar
- Press sort and then Go (no need to check the box for compute inversion index)