Describe how bubble sort works using adjacent comparisons and swaps
Trace a bubble sort through multiple passes showing each swap
State the best and worst case number of comparisons and passes
Write bubble sort in AQA pseudocode
How It Works
Bubble Sort — The Idea
Compare each pair of adjacent items. If they are in the wrong order, swap them. Repeat this process for multiple passes until no swaps occur in a complete pass (sorted!).
Key idea:Each pass "bubbles" the largest unsorted value to its correct position at the end of the list.
Optimisation:If a pass completes with zero swaps, the list is already sorted — stop early. This makes best case O(n).
Worked Example
Sorting [5, 3, 8, 1, 4]
Start:
5
3
8
1
4
Pass 1:
3
5
1
4
8
3 swaps — 8 now in place
Pass 2:
3
1
4
5
8
2 swaps — 5 now in place
Pass 3:
1
3
4
5
8
2 swaps
Pass 4:
1
3
4
5
8
0 swaps → DONE!
AQA Pseudocode
Bubble Sort in AQA Pseudocode
swapped ← True WHILE swapped = True swapped ← False FOR i ← 0 TO LEN(list) - 2 IF list[i] > list[i+1] THEN temp ← list[i] list[i] ← list[i+1] list[i+1] ← temp swapped ← True ENDIF ENDFOR ENDWHILE
Efficiency
Bubble Sort — Efficiency Analysis
Scenario
Comparisons
Passes
Best case (already sorted)
n-1 comparisons
1 pass
Worst case (reversed order)
~n² comparisons
n-1 passes
⚡ AQA Exam:Bubble sort becomes very slow for large lists. It's only practical for small datasets or nearly-sorted data.
Exam Practice
Have a go at this question
AQA-style question
Using bubble sort, show the state of the list [9, 4, 6, 2, 7] after Pass 1 and Pass 2. State how many swaps occurred in Pass 1.