Searching and Sorting · Cambridge syllabus 7.4 · Lesson 2 of 2
Bubble Sort
Bubble sort repeatedly compares adjacent elements and swaps those out of order. After an ascending pass, the largest remaining element has moved to the end of the unsorted region. A pass with no swaps can end the algorithm early.
By the end, you can
- Understand how bubble sort works.
- Trace passes through a list.
- Write a bubble-sort algorithm.
- Explain how adjacent values are compared and swapped.
Bubble sort
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 ← List[Index], List[Index] ← List[Index + 1], List[Index + 1] ← 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.
Worth remembering
- 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.
Worked example
One pass over [5, 2, 4] gives [2, 4, 5]. Further passes confirm the remaining order.
Practice
Warm-up · not marked
Check your understanding
Answer in your own words, then compare with the worked answer. Nothing here is saved or scored.
Worked answer
Compare and swap adjacent pairs to obtain [3, 2, 1, 4].
Check your method, units and explanation against it.
Marked practice
Set 1 of 4 · easiest first · Checked as you go, with the worked answer. Sign in or create a free account to save your progress.