Exam Frequency Analysis
Past paper frequency (2018 to 2024)
This topic accounts for approximately 7% of your exam marks.
stable
Low
Stable7%
Bubble sort traces and binary search descriptions appear in nearly every paper. 4 to 6 marks.
A bubble sort walks through a list over and over, comparing each pair of neighbouring values and swapping any pair that is out of order. The list is sorted as soon as a complete pass finishes without making any swaps.
The name comes from the way larger values "bubble" to the end of the list (or smaller values bubble to the beginning, depending on the sort direction).
Step-by-step algorithm
| Step | What it does |
|---|---|
| 1 | Look at the pair of values sitting at positions 1 and 2 |
| 2 | If that pair is out of order, swap the two values |
| 3 | Slide one position to the right (positions 2 and 3, then 3 and 4, and so on) |
| 4 | Keep applying steps 2 and 3 until the last pair has been processed. That whole sweep counts as one pass |
| 5 | If any swaps were made during the pass, start a new pass from the beginning |
| 6 | If no swaps were made during a pass, the list is sorted; stop |
After each pass, the largest unsorted value is in its correct position at the end of the list. This means you only need to compare up to one fewer position on each subsequent pass, although exam answers usually keep it simple and pass over the whole list each time.
Pseudocode
DECLARE Swapped : BOOLEAN
DECLARE n : INTEGER
n ← LENGTH(Data)
Swapped ← TRUE
WHILE Swapped = TRUE DO
Swapped ← FALSE
FOR i ← 1 TO n - 1
IF Data[i] > Data[i + 1] THEN
// Swap the two values
Temp ← Data[i]
Data[i] ← Data[i + 1]
Data[i + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT i
ENDWHILE
Example — Apply a bubble sort to the list [7, 3, 8, 2, 5].
Pass 1 (starting list [7, 3, 8, 2, 5]):
| Pair compared | Swap? | List after |
|---|---|---|
| 7, 3 | Swap | [3, 7, 8, 2, 5] |
| 7, 8 | No | [3, 7, 8, 2, 5] |
| 8, 2 | Swap | [3, 7, 2, 8, 5] |
| 8, 5 | Swap | [3, 7, 2, 5, 8] |
End of pass 1. The largest value (8) has bubbled to the end. Swaps were made, so continue.
Pass 2 ([3, 7, 2, 5, 8]):
| Pair compared | Swap? | List after |
|---|---|---|
| 3, 7 | No | [3, 7, 2, 5, 8] |
| 7, 2 | Swap | [3, 2, 7, 5, 8] |
| 7, 5 | Swap | [3, 2, 5, 7, 8] |
| 7, 8 | No | [3, 2, 5, 7, 8] |
End of pass 2. Swaps were made; continue.
Pass 3 ([3, 2, 5, 7, 8]):
| Pair compared | Swap? | List after |
|---|---|---|
| 3, 2 | Swap | [2, 3, 5, 7, 8] |
| 3, 5 | No | [2, 3, 5, 7, 8] |
| 5, 7 | No | [2, 3, 5, 7, 8] |
| 7, 8 | No | [2, 3, 5, 7, 8] |
End of pass 3. Swaps were made; continue.
Pass 4 ([2, 3, 5, 7, 8]):
| Pair compared | Swap? |
|---|---|
| 2, 3 | No |
| 3, 5 | No |
| 5, 7 | No |
| 7, 8 | No |
End of pass 4. No swaps were made. The list is sorted; the algorithm stops.
Final list
[2, 3, 5, 7, 8]
How the algorithm terminates
The bubble sort stops when a complete pass is made with no swaps. This is detected using a flag variable (often called Swapped):
- Set
Swappedto TRUE before each pass starts. - Every time a swap is made, set
Swappedto TRUE. - At the end of each pass, check
Swapped. If it is FALSE, the list is sorted; if it is TRUE, do another pass.
Without this flag, a naive bubble sort would always run the same number of passes, even on an already-sorted list. The flag lets the algorithm stop as soon as the list is in order.
Advantages and disadvantages
| Advantages | Disadvantages |
|---|---|
| Very simple to understand and code | Slow on large lists: up to n × n comparisons |
| Easy to spot when the list is sorted (no swaps in the pass) | Many swaps mean a lot of data movement |
| Sorts the list in place: needs no extra memory beyond a temporary variable | Better-performing algorithms exist (quicksort, mergesort), but they are beyond IGCSE |
Performance
For a list of n items:
- Best case (list already sorted): one pass, n − 1 comparisons, zero swaps.
- Worst case (list sorted in reverse): n × n comparisons and swaps.
Bubble sort is fine for short lists or educational examples, but not for serious sorting work.
