DSA Sorting

Bubble Sort

You need to explain why a leaderboard can freeze after a tiny reorder rule: each pass only fixes adjacent pairs. Correctness is easy to see; the cost of clearing every is not.

Bubble sort is a teaching algorithm for local disorder, loop invariants, and the price of write-heavy quadratic work. It is and when coded carefully, and partly with an early-exit flag.

Stable

Yes, with a strict > comparison

In place

Yes, Θ(1) auxiliary space

Adaptive

Partly, with an early-exit flag

Algorithm journey

Scan neighbors

Compare adjacent pairs left to right.

Clear one inversion

Swap when left > right; equal keys stay put.

Settle a suffix max

Each pass places at least one final rightmost value.

Stop early if sorted

A clean pass proves zero remaining inversions.

What actually happens

Naive idea: keep swapping any out-of-order neighbors until the array “looks sorted.” That works on a whiteboard of five numbers. At n = 10⁴ reverse-sorted keys you can face about 5 × 10⁷ swaps: well past a comfortable interactive budget.

Better framing: each left-to-right pass does not vaguely improve order. It proves a new final position for the active maximum and shrinks the unsettled prefix. The early-exit flag turns “already sorted” into Θ(n) comparisons.

The design still fails as a production default: few inversions can still cost Θ(n²) comparisons (a single turtle value crawling left), and the write volume stays high. Prefer insertion sort for tiny nearly sorted ranges, or an O(n log n) comparison sort as n grows. Comparison sorts cannot beat Ω(n log n) in the worst case on arbitrary keys; bubble never escapes the quadratic regime for many natural inputs.

Invariant

Before pass p, the suffix a[n-p:n] holds the p largest values in final sorted order, and every active-prefix value is no greater than every value in that suffix.

How to choose bubble sort

1. Teaching or tiny n? Use it to prove adjacent swaps and suffix settlement. Avoid it as a library default past a few dozen elements.

2. Do you need stability and constant extra memory? Yes, with a strict comparator. Insertion sort usually matches those properties with better constants on nearly sorted data.

3. Is the input already ordered? Early exit helps. If disorder is sparse but deep (turtles), expect quadratic comparisons anyway.

Quantitative check

Reverse order of n = 10³ distinct keys: n(n − 1)/2 ≈ 5 × 10⁵ comparisons and the same number of swaps. Already sorted: n − 1 comparisons and zero swaps with early exit. Random permutations average about n(n − 1)/4 swaps.

What one pass proves

During a pass, the larger member of each compared pair moves right. By the time the scan reaches its boundary, the maximum of the active prefix has crossed every value to its right and must be at that boundary. The algorithm does not merely make the array “more sorted”. It establishes one new final position.

Initialization

Before pass p, the last p positions already contain the p largest values in sorted order. For p = 0, this empty suffix is trivially correct.

Maintenance

The adjacent scan moves the maximum of indices [0, n − p) to n − p − 1 without touching the settled suffix.

Termination

After at most n − 1 passes, only one position remains. If a pass makes no swap, no adjacent inversion exists, which is equivalent to being sorted.

Outer-loop invariant: before pass p, the suffix a[n-p:n] is in final sorted order and every value in the active prefix is no greater than every value in that suffix.

Interactive: follow the comparisons and writes

Try duplicate keys to see stability, the nearly sorted input to trigger early exit, and reverse order to expose the exact worst case. Letters distinguish equal keys by their original identity.

Bubble pass laboratory

Compare adjacent neighbors; each completed pass fixes a suffix maximum.

The letters preserve original identity: watch whether 4a stays before 4b.

Pass 0 · start

Step 1 / 19

Comparisons

Array writes

Swaps

What changed

Start with the entire array active.

Invariant

Before pass 1, the final sorted suffix is empty.

active / comparingfinal suffix

Counting convention: one key comparison compares two values; one algorithmic assignment into an array cell is one write. During insertion, clearing the displayed source is only a conceptual gap animation, not an extra assignment. A swap uses two array writes (the temporary local variable is not counted).

Original visualizer · preserved

Interactive bubble sort demo

Watch adjacent comparisons move larger bars toward the settled suffix one swap at a time.

Speed:

ℹ️ Ready

Comparing/Active

Sorted

Reference implementation

Reset swapped at the start of every pass, exclude the settled suffix from the inner loop, and compare with > rather than >= to preserve equal-key order.

Python

python

def bubble_sort(a):
    n = len(a)

    for pass_no in range(n - 1):
        swapped = False
        end = n - pass_no - 1

        for j in range(end):
            if a[j] > a[j + 1]:       # strict: equal keys do not cross
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True

        if not swapped:               # already sorted
            break

    return a

Java

java

final class BubbleSort {
    static int[] sort(int[] a) {
        for (int pass = 0; pass < a.length - 1; pass++) {
            boolean swapped = false;
            int end = a.length - pass - 1;

            for (int j = 0; j < end; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    swapped = true;
                }
            }

            if (!swapped) break;
        }

        return a;
    }
}

Pass-by-pass trace

On [5, 1, 4, 2, 8], the third pass performs comparisons but no swaps. That observation is a proof that the whole array is sorted, so the fourth pass is unnecessary.

Pass	Array after pass	Work in pass	New fact
Start	[5, 1, 4, 2, 8]	n/a	No settled suffix yet
1	[1, 4, 2, 5, 8]	4 comparisons, 3 swaps	8 is final
2	[1, 2, 4, 5, 8]	3 comparisons, 1 swap	5, 8 are final
3	[1, 2, 4, 5, 8]	2 comparisons, 0 swaps	No inversion remains; stop

Cost model: comparisons are only half the story

Best case

Θ(n)

Already sorted: n − 1 comparisons, zero swaps, zero array writes, with early exit.

Average case

Θ(n²)

For a random permutation of distinct keys, expected inversions, and therefore swaps: are n(n − 1)/4.

Worst case

Θ(n²)

Reverse order: n(n − 1)/2 comparisons and swaps, or n(n − 1) array writes under a two-write swap model.

Swaps equal the inversion count

An inversion is a pair i < j with a[i] > a[j]. Every adjacent out-of-order swap removes exactly one inversion and cannot remove two. Because sorting ends at zero inversions, bubble sort performs exactly I swaps and 2I array writes.

Adaptivity has a limit

The flag makes a sorted input linear, but a small inversion count does not guarantee linear comparisons. In [2, 3, …, n, 1], only n − 1 inversions exist, yet the small value moves left just one position per left-to-right pass, so the algorithm still takes Θ(n²) comparisons.

Stability, space, and practical behavior

Stable

Strictly swapping only when left > right means equal records never cross. Using ≥ silently destroys this guarantee.

In place

The iterative implementation needs a temporary value, counters, and a flag: Θ(1) auxiliary space.

Not cache-efficient work

Scans are sequential, but repeated full passes and heavy writes dominate any locality advantage.

Not a production default

Insertion sort wins on most tiny or nearly sorted ranges; O(n log n) algorithms win as n grows.

Useful variants, and what they do not fix

Last-swap boundary

Remember the index of the final swap in a pass. Everything after it was already ordered, so the next scan can stop there. This can remove wasted comparisons but retains Θ(n²) worst-case time.

Cocktail shaker sort

Alternate left-to-right and right-to-left passes. Small “turtle” values can move left quickly, but asymptotic time is still Θ(n²). Strict comparisons keep it stable.

Recursive bubble sort

Recursing after each pass expresses the same invariant but adds Θ(n) call-stack space. It is usually worse than the direct loop and mainly appears as an exercise.

Edge cases and reasoning

Implementation checklist

Empty and one-element arrays execute zero passes.
Use j < n - pass - 1; reading a[j + 1] at the boundary is the classic bug.
Reset swapped = false for each pass, then test it only after the inner loop.
Apply the comparator consistently for descending order and custom record keys.
Count a swap only when values actually move; already ordered and all-equal inputs should write nothing.

Checks that sharpen the proof

Why is the rightmost active element final after one pass?
Why does “no adjacent inversion” imply the entire array is sorted?
Why is the swap count exactly the original inversion count?
What single character change makes the algorithm unstable?
Why can few swaps still coexist with quadratic comparisons?

Exercises

On [2, 3, …, n, 1], how many inversions exist, and why can comparisons still be Θ(n²)?
Change the comparator from > to >= on equal tagged keys. Which stability claim breaks, and on which first swap?
For n = 5 × 10³ reverse-sorted integers, estimate comparisons with and without early exit. When would you still prefer insertion sort?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): elementary sorting and loop invariants.
Knuth, The Art of Computer Programming, Vol. 3: adjacent-exchange sorting and inversion counting.
Sedgewick & Wayne, Algorithms: elementary sorts and stability definitions.

Takeaway

Bubble sort is a clean proof exercise: adjacent swaps remove one inversion at a time, and each pass fixes a suffix maximum. With early exit it is linear on already sorted data, but it remains write-heavy and quadratic on many simple inputs. Learn its invariant and counting arguments; choose insertion sort or an O(n log n) sort in real code.