Bubble sort: pedagogy, not production

A sorting algorithm that shows its work

Bubble sort is almost never the right answer in production. Its value is pedagogical: every comparison and swap is visible, and after each pass an honest correctness claim holds — the largest unsorted element has reached its final place. Students who see this clearly have a much easier time with more sophisticated sorts later.

public static void bubbleSort(int[] a) {
    int n = a.length;
    for (int pass = 0; pass < n - 1; pass++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - pass; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) return;  // already sorted
    }
}

Loop invariants that matter

• After pass p, the last p positions of the array contain the p largest values in sorted order.
• If a full pass executes with no swap, the array is already sorted — a legitimate early exit.

Complexity, honestly

In the worst case (reverse-sorted input) bubble sort makes Θ(n²) comparisons and swaps. Best case, with the early-exit optimization, on an already-sorted array, it makes Θ(n) comparisons and zero swaps. Memory is O(1) — it sorts in place. It is also stable: equal elements keep their relative order.

Open interactive lab →