Lesson 12 · Core algorithms

Bubble Sort: Passes, Swaps and Complexity

The simplest comparison sort: walk the array, swap neighbours that are out of order, repeat until a pass makes no swap.

What One Pass Actually Does

Bubble sort compares every adjacent pair and swaps the two values when the left one is larger. One left-to-right walk over the array is called a pass, and a pass does this:

Compare look at a[i] and a[i+1], the pair sitting next to each other.
Swap if out of order exchange them only when the left value is strictly greater. Equal values never move, which is what keeps the sort stable.
Step right move to the next pair and repeat to the end of the unsorted region.
Shrink the largest value has now bubbled to the end, so the next pass stops one position earlier.

The name comes from what a pass does to the largest value it meets. Once the walk reaches that value it keeps swapping it forward — the value travels right until the pass ends, and it lands in the last position. It has bubbled to the top.

That is the guarantee worth memorising, because everything else follows from it: after pass k, the final k positions hold the k largest values in sorted order. Those positions are finished, so pass k+1 can stop k steps earlier.

A pass = one sweep comparing a[i] with a[i+1] across the array
Each pass places at least one value in its permanent position
The sorted region grows from the right, never the left
Shrink the inner loop by one each pass or you re-scan sorted data

Counting the Comparisons

Pass 1 makes n−1 comparisons, pass 2 makes n−2, and so on down to 1. The total is the arithmetic series n(n−1)/2, which is Θ(n²) — the dominant term is n²/2.

Comparisons do not depend on the data: the loops run the same number of times whether the array arrives sorted, reversed, or shuffled. Only the number of swaps varies. A sorted array performs zero swaps; a reversed array performs one for every comparison, n(n−1)/2 of them.

This is why bubble sort is taught but not shipped. At n = 1,000 that is about half a million comparisons for work that merge sort finishes in roughly ten thousand.

How input order changes the work
Input	Comparisons	Swaps	Time
Already sorted	n(n−1)/2	0	O(n²), or O(n) with the flag
Random order	n(n−1)/2	≈ n²/4	O(n²)
Reverse sorted	n(n−1)/2	n(n−1)/2	O(n²)

Comparisons are fixed by the loop structure, not the input
Swaps are what the input order actually changes
Reverse-sorted input is the worst case for swap count
Space stays O(1) — every swap happens inside the array

Implementation

Sort with bubble sort

def bubble_sort(values):
    n = len(values)
    for i in range(n - 1):
        swapped = False
        # the last i entries are already final, so stop early
        for j in range(n - 1 - i):
            if values[j] > values[j + 1]:
                values[j], values[j + 1] = values[j + 1], values[j]
                swapped = True
        if not swapped:          # a clean pass means the array is sorted
            break
    return values


print(bubble_sort([5, 1, 4, 2, 8]))

#include <iostream>
#include <vector>
void bubbleSort(std::vector<int>& values) {
    const int n = static_cast<int>(values.size());
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        // the last i entries are already final, so stop early
        for (int j = 0; j < n - 1 - i; ++j) {
            if (values[j] > values[j + 1]) {
                std::swap(values[j], values[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // a clean pass means the array is sorted
    }
}
int main() {
    std::vector<int> values {
        5, 1, 4, 2, 8
    };
    bubbleSort(values);
    for (int v : values) std::cout << v << ' ';
    std::cout << '\n';
}

import java.util.Arrays;
public class BubbleSort {
    static void bubbleSort(int[] values) {
        int n = values.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            // the last i entries are already final, so stop early
            for (int j = 0; j < n - 1 - i; j++) {
                if (values[j] > values[j + 1]) {
                    int tmp = values[j];
                    values[j] = values[j + 1];
                    values[j + 1] = tmp;
                    swapped = true;
                }
            }
            if (!swapped) break; // a clean pass means the array is sorted
        }
    }
    public static void main(String[] args) {
        int[] values = {5, 1, 4, 2, 8};
        bubbleSort(values);
        System.out.println(Arrays.toString(values));
    }
}

Watch it run

Step through it

Running on [5, 1, 4, 2, 8]

Output

The Early-Exit Flag

The plain version keeps sweeping even after the array is sorted, because nothing tells it to stop. One boolean fixes that:

Before the pass set swapped = false. This happens at the top of every pass, not once at the start.
Inside the swap set swapped = true. Any exchange at all proves the array was not yet sorted.
After the pass if swapped is still false, no pair was out of order, so the array is sorted and the outer loop breaks.

This turns the best case from O(n²) into O(n): one pass over sorted data, no swaps, done. It costs one variable and one branch. Without it, [1,2,3,4,5] still runs every pass — this is the single change that makes the algorithm defensible on nearly sorted input.

swapped is reset at the top of every pass, not once at the start
No swap in a full pass proves sortedness — nothing is out of order
Best case drops to n−1 comparisons and zero swaps
Worst and average cases are unchanged at O(n²)

On paper: Five Values, Four Passes

Take [5, 1, 4, 2, 8]. Each line below is one full pass, with the settled tail marked off:

Pass 1 (5,1) swap, (5,4) swap, (5,2) swap, (5,8) no swap → [1, 4, 2, 5, 8], and 8 is final.
Pass 2 scans the first four only. (1,4) no swap, (4,2) swap, (4,5) no swap → [1, 2, 4, 5, 8], and 5 is final.
Pass 3 (1,2) and (2,4), nothing swaps. The flag stays false, so the loop breaks early.
Done 4 + 3 + 2 = 9 comparisons and 4 swaps.

Three passes, not four — the flag caught it. Writing out the array after each pass, with the settled tail marked, is what an exam answer needs: it shows the sorted region growing rather than just asserting the result.

Write the whole array after each pass, not after each swap
Mark the settled tail so the shrinking inner loop is visible
Pass 3 makes no swap, so the flag ends the sort early
Total: 4 + 3 + 2 = 9 comparisons and 4 swaps

Stability, and Where It Sits

Bubble sort is stable: it only swaps when the left value is strictly greater, so equal values never cross. If two records compare equal, the one that started earlier stays earlier — the property that lets you sort by one key and then another without destroying the first ordering.

It is also in-place (O(1) extra space) and adaptive once the flag is added, meaning nearly sorted input costs close to linear time.

Against its neighbours: insertion sort does the same O(n²) work but with far fewer writes and wins on almost every real input; selection sort makes fewer swaps but is not stable and is never adaptive. For anything large, merge sort or quick sort is the answer. Bubble sort earns its place as the clearest illustration of what a comparison sort is.

Stable, because the swap condition is strict > rather than >=
In-place with O(1) auxiliary memory
Adaptive only with the early-exit flag
Prefer insertion sort in practice — same bound, much less work

What One Pass Actually Does

Counting the Comparisons

Sort with bubble sort

Step through it

The Early-Exit Flag

On paper: Five Values, Four Passes

Stability, and Where It Sits

Continue this course

Sorting Algorithms: Methods and Performance

Selection Sort: Scan, Swap and Cost

Insertion Sort: Shifting, Gaps and Cost