Bubble Sort

AQA 4.3.5 — Bubble sort

Retrieval: Binary Search required its input to already be sorted. This lesson answers the obvious next question: how do you get an unsorted list into sorted order in the first place?

Bubble sort repeatedly steps through a list, comparing each pair of adjacent elements and swapping them if they're in the wrong order. Each full pass through the list "bubbles" the largest remaining unsorted value up to its correct position at the end.

def bubble_sort(items):
    n = len(items)
    for i in range(n):
        for j in range(n - 1 - i):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
    return items

Common mistake

Assuming one pass fully sorts the list. One pass only guarantees the single largest value reaches its final position — everything else may still be out of order and needs further passes. This is exactly why the outer loop runs multiple times, not once.

Trace it — one full sort

Tracing bubble_sort([5, 2, 4, 1]):

Pass	Comparisons (swap?)	List after pass
1	5,2→swap; 5,4→swap; 5,1→swap	[2, 4, 1, 5]
2	2,4→no; 4,1→swap	[2, 1, 4, 5]
3	2,1→swap	[1, 2, 4, 5]

The list is fully sorted after pass 3 (for 4 items, at most 3 passes are ever needed) — but the algorithm above doesn't know that and keeps checking anyway, which is exactly the inefficiency the next section addresses.

Debug it — find the error

def broken_bubble_sort(items):
    n = len(items)
    for i in range(n):
        for j in range(n - i):        # bug is on this line
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
    return items

Run this mentally (or for real) against [3, 1, 2] — it crashes with an IndexError. Identify exactly why range(n - i) is wrong here, and state the correct expression (compare it against the working version above).

Evaluating efficiency

The version above always performs the full number of passes even if the list becomes sorted early. A common optimisation: track whether any swap happened during a pass — if not, the list is already sorted and the algorithm can stop immediately, rather than needlessly checking already-sorted data.

Challenge

Implement bubble sort with the early-completion optimisation described above (stop as soon as a full pass makes zero swaps), and test it on an already-sorted list to confirm it now finishes in a single pass instead of running the full number of passes regardless.

Looking ahead: the next lesson (Insertion Sort) is a genuinely different sorting strategy — you'll compare the two directly, not just learn them as isolated methods.

Learn