Imagine a row of kids who need to stand in order from shortest to tallest. You don't try to fix the whole line at once. You just look at two kids standing next to each other: if the one on the left is taller, the two of them swap places. Then you slide one step to the right and check the next pair. By the time you reach the end of the line, the tallest kid has been carried all the way to the far end — they "bubbled" to the top. That single rule, compare two neighbors and swap them if they're out of order, is the whole of Bubble Sort.
Call the number of items $n$. One left-to-right sweep is a pass. Each pass guarantees that the largest remaining value reaches its correct spot at the right end, so the next pass can stop one cell earlier. With $n$ items, the first pass makes $n-1$ comparisons, the next makes $n-2$, and so on down to $1$. For a tiny list of $n=5$ items in the worst order, that's $4+3+2+1 = 10$ comparisons to finish.
That sum grows like $\tfrac{1}{2}n^2$, so we say Bubble Sort runs in $\mathcal{O}(n^2)$ time: double the list and the work roughly quadruples. Every swap fixes exactly one inversion (an out-of-order neighbor pair), so the swap count equals the number of inversions in your data. There is one rescue: keep a swapped flag. If a whole pass makes zero swaps, the list is already in order and you can stop immediately — that turns an already-sorted input into a single $n-1$ comparison sweep, the best case $\mathcal{O}(n)$. The Input Size slider sets $n$, and the Preset menu chooses how scrambled the starting data is.
Try this in the sim above: (1) pick the Reverse sorted preset and watch every single comparison turn into a swap — the slowest case. (2) Pick Already sorted and step through: the early-exit flag halts after just one clean pass. (3) Pick Nearly sorted and count how few passes it takes — proof that the swapped flag rewards almost-ordered data.
Bubble Sort is one of the simplest comparison-based sorting algorithms. Though its exact origin is debated, it was formally analyzed by Iverson (1962) and popularized in early computer science curricula. The name derives from the way larger elements "bubble up" to the top of the array. Despite its pedagogical value, it is rarely used in production due to its O(n²) worst-case complexity.
| Symbol | Meaning | Range |
|---|---|---|
| \(n\) | Input array size | \(\mathbb{Z}^+\) |
| \(T(n)\) | Number of comparisons | \([n-1, \frac{n(n-1)}{2}]\) |
| \(W(n)\) | Worst-case comparisons | \(\frac{n(n-1)}{2}\) |
| \(B(n)\) | Best-case comparisons (optimized) | \(n-1\) |
| \(i\) | Outer loop pass index | \(0 \leq i \leq n-2\) |
| \(j\) | Inner loop comparison index | \(0 \leq j \leq n-i-2\) |
| \(S(n)\) | Number of swaps (worst case) | \(\frac{n(n-1)}{2}\) |
In pass \(i\) (0-indexed), the inner loop runs from \(j=0\) to \(j = n-i-2\), performing \(n-i-1\) comparisons.
$$\text{Comparisons in pass } i = n - i - 1$$If the array is already sorted, the first pass completes with no swaps. The swapped flag triggers an early exit after just one pass of \(n-1\) comparisons:
On average over all \(n!\) permutations, each element travels roughly \(\frac{n}{4}\) positions. The expected comparisons and swaps are both \(\Theta(n^2)\):
$$A(n) \approx \frac{n^2}{4} \implies \Theta(n^2)$$Worst case (reverse-sorted input): every comparison results in a swap. Number of swaps equals number of inversions in the input, maximum \(\binom{n}{2}\):
$$S_{\max}(n) = \binom{n}{2} = \frac{n(n-1)}{2} = \Theta(n^2)$$Bubble sort is in-place. Only a constant number of variables (\(i, j, \text{swapped}, \text{temp}\)) are needed regardless of input size:
$$\text{Space} = \mathcal{O}(1) \text{ auxiliary}$$Bubble sort is stable: equal elements are never swapped (the condition is strict \(>\), not \(\geq\)), so their relative order is preserved.
Array: [5, 3, 8, 1, 9, 2]
Pass 0: Compare (5,3)→swap→[3,5,8,1,9,2]; (5,8)→no swap; (8,1)→swap→[3,5,1,8,9,2]; (8,9)→no swap; (9,2)→swap→[3,5,1,8,2,9]. Swaps: 3. Element 9 is now in final position.
Pass 1: Compare (3,5)→no swap; (5,1)→swap→[3,1,5,8,2,9]; (5,8)→no swap; (8,2)→swap→[3,1,5,2,8,9]. Swaps: 2.
Pass 2: Compare (3,1)→swap→[1,3,5,2,8,9]; (3,5)→no swap; (5,2)→swap→[1,3,2,5,8,9]. Swaps: 2.
Pass 3: Compare (1,3)→no swap; (3,2)→swap→[1,2,3,5,8,9]. Swaps: 1.
Pass 4: Compare (1,2)→no swap. swapped=false → early exit!
Final: [1,2,3,5,8,9]. Total comparisons: 15 (passes do 5+4+3+2+1). Total swaps: 8.
swapped flag), if a pass completes with zero swaps, the array is sorted and the algorithm terminates immediately. For a nearly-sorted array with only a few inversions, this can mean just 1–2 passes — making it \(\mathcal{O}(n)\). Insertion Sort has the same property and is generally preferred, but Bubble Sort with early-exit is competitive on this specific input class. This is why benchmarks sometimes show Bubble Sort "winning" when testers accidentally test on nearly-sorted data.
swapped flag) optimization, Bubble Sort exits after the first pass that makes no swaps. On an already-sorted array, this gives best-case \(\mathcal{O}(n)\). Without this optimization, yes — even a sorted input takes \(\frac{n(n-1)}{2}\) comparisons. The unoptimized version always runs all \(n-1\) passes regardless of input order.A[j] > A[j+1] (not ≥) is unconditionally stable — equal elements are never swapped, preserving their original order. It is only unstable if you carelessly change the condition to ≥. This stability is a genuine advantage over QuickSort and HeapSort in cases where maintaining relative order of equal elements matters (e.g., multi-key sorting).for j in range(n-1) — doesn't shrink the inner loop after each pass.for j in range(n-i-1) — the last \(i\) elements are already sorted and don't need rechecking. Without this, the algorithm does \(n \cdot (n-1)\) comparisons instead of \(\frac{n(n-1)}{2}\), doubling the work.if not swapped: break inside the j-loop.