Sorting

Bubble Sort

Sweep through the list swapping out-of-order neighbors; the largest value "bubbles" to the end each pass.

Green is the locked-in sorted tail — the invariant. Orange is the larger of the compared pair (it bubbles right); blue is its smaller neighbor.

What you're seeing

Each bar is a number; taller is larger. Bubble sort sweeps left to right comparing each pair of neighbors and swapping them if they're out of order. The effect of one full sweep is that the largest value present "bubbles" all the way to the right end — so the green sorted tail grows by one each pass, from the right. Watch the orange (larger) bar repeatedly hop rightward until it settles.

The rule

bubble_sort(a):
    for end = n-1 down to 1:
        swapped = false
        for j = 0 .. end-1:
            if a[j] > a[j+1]:
                swap(a[j], a[j+1])     # bubble the larger one right
                swapped = true
        if not swapped: break          # already sorted — stop early

The swapped flag is what makes this version adaptive: one clean pass with no swaps proves the array is sorted, so it stops.

The invariant

After pass k, the k largest values occupy their final sorted positions at the end of the array — the suffix a[n−k..n) is sorted and every value in it is ≥ everything before it. It holds trivially before pass 1 (empty suffix). Each pass maintains it: a left-to-right sweep over the still-unsorted prefix always carries that prefix's maximum to the prefix's last slot — extending the sorted suffix by one. After n−1 passes the suffix is the whole array. The early-exit is sound too: if a pass performs no swaps, no adjacent pair is out of order, which for a total order means the entire array is sorted.

The cost

BestAverageWorst Comparisonsn−1Θ(n²)Θ(n²) Swaps0Θ(n²)Θ(n²) SpaceO(1)O(1)O(1)

With the early-exit flag, an already-sorted input costs a single pass — n−1 comparisons, zero swaps (try it). Reversed input is the worst case: every pair is out of order every pass, giving n(n−1)/2 comparisons and n(n−1)/2 swaps. That double-Θ(n²) — bubble sort moves data as often as it compares it — is exactly why it loses to insertion sort, which does the same comparisons but far fewer moves. Bubble sort is stable and in-place.

In the wild

Honestly: essentially nowhere, by design choice. Bubble sort is the textbook example of an algorithm that is correct, simple to state, and a poor choice in practice — it is slower than insertion sort on the same inputs (more swaps) while offering no compensating advantage. Donald Knuth's verdict is often quoted: "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems." Its real value is pedagogical: it is the cleanest illustration of an adaptive early-exit and of a suffix-growing invariant — which is why it earns a place here, clearly labeled as a teaching tool rather than a tool.

Try this

Set Already sorted and watch it finish in one pass (the early-exit). Then set Reversed and watch both counters — comparisons and swaps — climb together to n(n−1)/2. Compare that swap count with selection sort's n−1 on the same input: same comparisons, wildly different data movement.

References

  1. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching, §5.2.2 (Sorting by Exchanging) — analysis and the famous "nothing to recommend it" remark. Addison-Wesley.
  2. Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), Problem 2-2 (bubble sort correctness and the loop invariant). MIT Press, 2022.
  3. Sedgewick & Wayne. Algorithms, 4th ed., §2.1 — elementary sorts and the comparison/exchange cost model. algs4.cs.princeton.edu/21elementary.