GCSE Computer Science

Python bubble sort — GCSE Computer Science

What bubble sort does

Bubble sort works through a list comparing each pair of neighbouring items. If they're in the wrong order, it swaps them. Repeat that process enough times, and the list ends up sorted. It isn't the fastest sorting algorithm — GCSE specifications teach it because the mechanism is easy to trace by hand, not because it's what real systems use for large datasets.

The pass-by-pass comparison mechanism

Each full sweep through the list is called a pass. On a single pass, bubble sort compares item 1 with item 2, then item 2 with item 3, and so on to the end of the list — swapping whenever the left item is bigger than the right one. By the end of one pass, the largest unsorted value has "bubbled" all the way to its correct position at the end of the list. That's the only guarantee one pass gives you.

Trace [5, 2, 8, 1] through one pass: compare 5 and 2 → swap → [2, 5, 8, 1]. Compare 5 and 8 → no swap. Compare 8 and 1 → swap → [2, 5, 1, 8]. One pass, and the largest value (8) has already reached the end.

A worked Python implementation

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

The outer loop counts the passes. The inner loop does the comparing and swapping — and it gets one step shorter on every pass, because n - 1 - i shrinks as i increases. That's not an accident: the last i items are already in their final position after each pass, so there's no need to keep comparing them.

How many passes are needed

In the worst case, a list of n items needs n - 1 passes to guarantee it's fully sorted. Each pass fixes at least one more value into its correct position at the end of the list, so after n - 1 passes, everything is in place.

The optimisation: detecting an already-sorted list

def bubble_sort(numbers):
    n = len(numbers)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
                swapped = True
        if not swapped:
            break
    return numbers

If a full pass makes no swaps at all, the list is already sorted — there's no point continuing. Setting a swapped flag and breaking out early when it stays False turns bubble sort's worst case into its best case whenever the data is already in order.

What examiners actually test

GCSE questions on bubble sort usually ask you to trace a sort step by step, count how many passes a given list needs, or state the list's contents after a specific number of passes. Write out the list after every single comparison, not just after each full pass — an intermediate swap is easy to lose track of otherwise.