Knowledge organisersSearching and sorting algorithms

Standard sorting algorithms: Bubble sort

Knowledge organiser

Searching and sorting algorithms

2.1.3c

Understand the main steps of each algorithm, Understand any pre-requisites of an algorithm, Apply the algorithm to a data set, Identify an algorithm if given the code or pseudocode for it

What you need to know

Bubble sort is a simple sorting algorithm that repeatedly goes through a list, comparing adjacent pairs of items and swapping them if they are in the wrong order. Each full pass through the list 'bubbles' the largest unsorted item to its correct position. The algorithm continues making passes until no swaps are needed, meaning the list is sorted.

Key points

Compare each pair of ADJACENT items and swap them if they are in the wrong order.
After each pass, the largest unsorted item 'bubbles up' to its correct position at the END of the list.
The sorted section builds from the RIGHT (end) of the array.
Each new pass requires one fewer comparison because the end of the list is already sorted.
The algorithm makes a FINAL pass with no swaps to confirm the list is sorted, then stops.
Needs MULTIPLE PASSES through the data — a value may be repeatedly swapped until it reaches its correct position.
Simple to understand and implement, but inefficient for large or heavily unsorted datasets.
SIMILARITIES WITH INSERTION SORT: both sort in place, both use loops/iteration, both compare pairs of values, both swap values, both use a temporary variable, both build a sorted list one item at a time.
DIFFERENCES FROM INSERTION SORT: bubble sort builds sorted section from the END; insertion sort builds it from the START. Insertion sort is generally more efficient on average.

Code examples

Bubble sort in Python

python

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

print(bubble_sort([3, 2, 9, 10, 7]))
# Output: [2, 3, 7, 9, 10]

def bubble_sort(data): n = len(data) for i in range(n - 1): for j in range(n - 1 - i): if data[j] > data[j + 1]: data[j], data[j + 1] = data[j + 1], data[j] return data print(bubble_sort([3, 2, 9, 10, 7])) # Output: [2, 3, 7, 9, 10]