Sorting and Searching Algorithms
Algorithm Design and Problem Solving · 4 question types
Exam Frequency Analysis
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 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 Count : INTEGER
Count ← LENGTH(Data)
Swapped ← TRUE
WHILE Swapped = TRUE DO
Swapped ← FALSE
FOR i ← 1 TO Count - 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
Tracing one complete pass of a bubble sort
Start with the unsorted list: 6, 2, 9, 4, 1 (five values). A single pass compares every neighbouring pair in turn and swaps any that are out of order.
Solution:
- Compare 6 and 2: 6 > 2, so swap → list is now 2, 6, 9, 4, 1
- Compare 6 and 9: 6 < 9, no swap → list stays 2, 6, 9, 4, 1
- Compare 9 and 4: 9 > 4, so swap → list is now 2, 6, 4, 9, 1
- Compare 9 and 1: 9 > 1, so swap → list is now 2, 6, 4, 1, 9
After one complete pass, the largest value (9) has bubbled to its correct position at the end. Three swaps were made, so Swapped is TRUE and a second pass will begin. On the next pass the algorithm only needs to compare up to position 4, since position 5 is already settled.
How the algorithm terminates
The bubble sort stops when a complete pass is made with no swaps. This is detected using a (often called Swapped):
- Set
Swappedto FALSE at the start of each pass. - 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.
Explaining why a bubble sort is efficient
What comes up: a 3-mark question asks you to explain what features of a bubble sort algorithm make it efficient (not just how the algorithm works).
Write (up to three marks): (1) A Boolean flag variable is set to FALSE at the start of each pass and only changed to TRUE if a swap is made during that pass.
(2) If a complete pass finishes with the flag still FALSE, no swaps occurred, so the list must already be sorted and the algorithm stops immediately rather than making unnecessary passes.
(3) The upper limit of the inner loop is reduced by one after each pass, because the largest value from that pass is now in its final position at the end and no longer needs to be compared.
Watch out: saying the algorithm is efficient just because "it stops when sorted" earns only partial credit. The examiner wants you to explain the mechanism: the flag detects a pass with no swaps, and the reducing inner-loop limit cuts the number of comparisons on every subsequent pass.
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 this level |
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.
