What is Bubble Sort?
Bubble sort is a sorting algorithm that repeatedly compares adjacent pairs of elements and swaps them if they are in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position at the end.
The algorithm requires multiple passes through the list, and stops when a complete pass makes no swaps (the list is sorted).
How Bubble Sort Works — Step by Step
- Compare element at index 0 with element at index 1
- If they are in the wrong order (larger first), swap them
- Move to the next pair (index 1 and 2), repeat
- Continue to the end of the unsorted portion
- After each pass, the largest remaining element is in its final position
- Repeat until no swaps occur in a full pass
Worked Example — Sort [5, 3, 8, 1, 9, 2]
Pass 1
After pass 1: [3, 5, 1, 8, 2, 9] — 9 is in its final position ✓
Pass 2 (only compare first 5 elements)
After pass 2: [3, 1, 5, 2, 8, 9] — 8 in final position ✓
Passes continue until a full pass makes no swaps — the list is sorted.
Trace Table — Passes Summary for [5, 3, 8, 1, 9, 2]
| Pass | List after pass | Swaps made? |
|---|
| 1 | [3, 5, 1, 8, 2, 9] | Yes (3 swaps) |
| 2 | [3, 1, 5, 2, 8, 9] | Yes (2 swaps) |
| 3 | [1, 3, 2, 5, 8, 9] | Yes (2 swaps) |
| 4 | [1, 2, 3, 5, 8, 9] | Yes (1 swap) |
| 5 | [1, 2, 3, 5, 8, 9] | No → STOP |
AQA Pseudo-code
SUBROUTINE bubbleSort(list)
n ← LEN(list)
swapped ← True
WHILE swapped = True
swapped ← False
FOR i ← 0 TO n - 2
IF list[i] > list[i + 1] THEN
temp ← list[i] // swap using temp variable
list[i] ← list[i + 1]
list[i + 1] ← temp
swapped ← True
ENDIF
ENDFOR
ENDWHILE
RETURN list
ENDSUBROUTINE
Key Points About Bubble Sort
| Property | Detail |
|---|
| Worst case comparisons | ~n² / 2 (approximately n²) |
| n = 1,000 items | ~1,000,000 comparisons in worst case |
| Works on unsorted lists? | Yes — works on any list |
| Early termination | Stops as soon as no swaps in one pass (optimisation) |
| Swap mechanism | Requires a temp variable to swap without data loss |
Exam tip: Always use a temp variable when describing or writing a swap — you cannot just write list[i] ← list[i+1] directly. The optimisation of stopping when no swaps occur is important — mention it in exam answers.
⚠️ Common Mistakes
- Swapping without a temp variable — this overwrites data. Always use temp ← list[i]; list[i] ← list[i+1]; list[i+1] ← temp
- Forgetting the optimisation: bubble sort can stop early if no swaps were made in a pass
- Getting the FOR loop bound wrong: loop runs from 0 TO n-2 (not n-1) to avoid going out of bounds
- Confusing which element "bubbles up" — the largest element moves to the end first