Algorithm Design and Problem Solving · 4 question types
Past paper frequency (2018 to 2024)
This topic accounts for approximately 7% of your exam marks.
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 | 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.
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.
[2, 3, 5, 7, 8]
The bubble sort stops when a complete pass is made with no swaps. This is detected using a flag variable (often called Swapped):
Swapped to TRUE before each pass starts.Swapped to TRUE.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 | 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 |
For a list of n items:
Bubble sort is fine for short lists or educational examples, but not for serious sorting work.
