7.3b Bubble Sort — Cambridge IGCSE CS 0478

What is Bubble Sort?

Bubble sort is a simple sorting algorithm that works by repeatedly comparing adjacent pairs of elements and swapping them if they are in the wrong order. Larger values "bubble up" to the end of the list after each pass.

How it works — the algorithm

Make multiple passes through the list
On each pass, compare each adjacent pair: if the left item is bigger than the right, swap them
After each complete pass, the largest unsorted item is in its correct position at the end
Repeat passes until no swaps are made in a full pass (the list is sorted)

Cambridge Pseudocode — Bubble Sort

n ← length_of_list
swapped ← TRUE
WHILE swapped = TRUE DO
    swapped ← FALSE
    FOR i ← 1 TO n - 1
        IF list[i] > list[i + 1] THEN
            temp ← list[i]
            list[i] ← list[i + 1]
            list[i + 1] ← temp
            swapped ← TRUE
        ENDIF
    NEXT i
    n ← n - 1
ENDWHILE

Key exam point: The temp variable is essential for swapping — you must store one value temporarily while overwriting it. Without temp, data would be lost. Also note: n ← n - 1 is an optimisation — after each pass, the last item is already sorted, so you can ignore it.

Step-by-step example — sorting: 5, 3, 8, 1, 4

Start

53814

Pass 1 — comparisons and swaps

5>3 → swap | 5<8 → no swap | 8>1 → swap | 8>4 → swap

35148

✓ 8 is now in position

Pass 2

3<5 → no | 5>1 → swap | 5>4 → swap

31458

Pass 3

3>1 → swap | 3<4 → no

13458

Pass 4 — no swaps made → sorted!

13458

Key details about bubble sort

Property	Detail
Maximum passes (n items)	n − 1 passes in the worst case
Comparisons per pass	Decreases by 1 each pass (optimised version)
Early termination	Stops if a pass completes with no swaps (already sorted)
Stability	Stable — equal elements keep their original relative order
In-place	Yes — only needs one extra variable (temp) for swapping

⚠️ Common Mistakes

Forgetting the temp variable when swapping — writing list[i] ← list[i+1] directly destroys the original value
Setting the FOR loop to go TO n instead of TO n-1 (this would compare list[n] with list[n+1] which doesn't exist)
Not resetting swapped to FALSE at the start of each pass
In exam questions about "number of passes", remember each pass puts ONE more item in its final position

▶

Video coming soon

Click slide or press arrow keys to navigate

✍️

Worksheet — Bubble Sort

5 questions · 12 marks

Q1Explain how a bubble sort works. [3]

✅ Mark scheme

Adjacent pairs of items are compared [1]; if they are in the wrong order they are swapped [1]; this is repeated for multiple passes until no swaps occur in a pass / the list is sorted [1]

Q2Show the state of the list after EACH pass of bubble sort on: 7, 2, 9, 4, 6. [4]

✅ Mark scheme

Pass 1: 2, 7, 4, 6, 9 [1]; Pass 2: 2, 4, 6, 7, 9 [1]; Pass 3: 2, 4, 6, 7, 9 (no swaps — sorted) [1]; 3 passes needed [1]

Q3Why is a temporary variable (temp) needed when swapping two elements? [2]

✅ Mark scheme

When you assign list[i] ← list[i+1], the original value of list[i] is overwritten/lost [1]; temp stores the original value of list[i] so it can be assigned to list[i+1] afterwards [1]

Q4What is the purpose of the 'swapped' flag in an optimised bubble sort? [2]

✅ Mark scheme

It detects whether any swaps were made during a pass [1]; if no swaps were made, the list is already sorted and the algorithm can stop early without doing unnecessary extra passes [1]

Q5For a list of 6 items that is already sorted, how many passes does optimised bubble sort make? [1]

✅ Mark scheme

Just 1 pass [1] — the first pass makes no swaps, so the swapped flag stays FALSE and the algorithm terminates immediately.

Quiz — Bubble Sort

Q 1 of 8

Score

/ 8

Click to reveal

Term	Definition

🔒

Pro Content

Upgrade to access all lessons.

£7.99/month

or £59/year

Subscribe now →

What is Bubble Sort?

How it works — the algorithm

Cambridge Pseudocode — Bubble Sort

Step-by-step example — sorting: 5, 3, 8, 1, 4

Key details about bubble sort

Worksheet — Bubble Sort

Mini Test — Bubble Sort