The lesson: Bubble Sort
Bubble sort
In this section
- Understand how bubble sort works.
- Trace passes through a list.
- Write a bubble-sort algorithm.
- Explain how adjacent values are compared and swapped.
A bubble sort puts a list in order by comparing each pair of adjacent items and swapping them if they are the wrong way round, repeating until a whole pass makes no swaps at all.
Follow 5, 3, 8, 1 through one pass. Compare 5 and 3: wrong order, swap, giving 3, 5, 8, 1. Compare 5 and 8: correct, leave them. Compare 8 and 1: swap, giving 3, 5, 1, 8. The pass is over and 8, the largest value, has reached the end — which is what happens on every pass, and is why each pass can stop one place earlier than the last.
The second pass gives 3, 1, 5, 8 and the third 1, 3, 5, 8. A fourth pass makes no swaps, which is how the algorithm knows to stop.
The structure is two nested loops: an outer loop over the passes, an inner loop over the adjacent pairs within a pass, and a swap inside that. The swap needs a temporary variable — temp ← a, a ← b, b ← temp — because assigning one to the other directly destroys the value you still need.
A flag set to False at the start of each pass and to True on any swap is what makes the algorithm stop early: if a pass completes with the flag still False, the list is already sorted and no further pass can change it. Bubble sort is simple to write and easy to trace, and it is slow on a large list, because the number of comparisons grows with the square of the number of items.
Key points
- Compare adjacent pairs and swap if out of order; repeat until a pass makes no swaps.
- Each pass carries the largest remaining value to the end.
- A swap needs a temporary variable, or one of the two values is lost.