Bubble sort
One pass at a time
Ascending order means smallest first, going up (2, 5, 9).
Descending order means largest first, going down (9, 5, 2). Unless a question says otherwise, sorts put numbers into ascending order.
A bubble sort goes along the list comparing each pair of neighbours. If a pair is in the wrong order, it swaps them. One trip along the list is a pass.
After the first pass, the largest item has "bubbled" to the end and is in its final place. So each pass can stop one place earlier than the one before.
A worked example: the first pass of a bubble sort on 14, 9, 22, 6, 17, into ascending order.
- Compare 14 and 9. 14 is bigger, so swap: 9, 14, 22, 6, 17.
- Compare 14 and 22. They are in order: no swap.
- Compare 22 and 6. 22 is bigger, so swap: 9, 14, 6, 22, 17.
- Compare 22 and 17. 22 is bigger, so swap: 9, 14, 6, 17, 22.
- The pass is over. It made 4 comparisons and 3 swaps. The largest item, 22, is now at the end.
Counting comparisons: a list of n items has n − 1 neighbouring pairs, so the first pass makes n − 1 comparisons. If each pass stops one place earlier, the second pass makes n − 2, the third n − 3, and so on.
A swap is only counted when a pair is out of order, so a pass can make fewer swaps than comparisons.
When does it stop?
The sort repeats passes until a pass makes no swaps.
Only then does it know the list is sorted.
- A list can be in order after pass 2, but the algorithm only finds out in pass 3, which makes no swaps.
- A list of n items needs at most n − 1 passes.
- For descending order, swap when the left item is smaller. For words, compare alphabetically.
- Write the list. Compare items 0 and 1, swap if needed, and write the list again if it changed.
- Move along one place: compare items 1 and 2, and so on to the end.
- That is one pass. Write the list as it stands.
Carrying on the worked example until it stops:
- After pass 1: 9, 14, 6, 17, 22 (3 swaps).
- Pass 2 compares 9 and 14 (no swap), 14 and 6 (swap), 14 and 17 (no swap): 9, 6, 14, 17, 22 (1 swap).
- Pass 3 compares 9 and 6 (swap), 9 and 14 (no swap): 6, 9, 14, 17, 22 (1 swap). The list is now in order.
- Pass 4 compares 6 and 9: no swap. A pass with no swaps, so the sort stops.
- In total: 4 passes, 5 swaps, and 4 + 3 + 2 + 1 = 10 comparisons.
A very common mistake is to write the fully sorted list when the question asks for the list after one pass.
Loading the question