Algorithms · foundation
Bubble sort
Bubble sort repeatedly compares adjacent elements and swaps inverted pairs, moving an extreme element to its final position on each complete pass.
Why it matters
Bubble sort is rarely a production choice, but its simple invariant makes sorting correctness, stability, adaptiveness, and quadratic growth visible.
Mental model
How to reason about bubble sort
After one left-to-right pass, the largest remaining element has crossed every smaller neighbor and reached the unsorted region's right edge; that suffix is then fixed.
Analogy
Larger bubbles rise one position whenever they meet a smaller neighbor, eventually reaching the surface after enough adjacent exchanges.
Examples
See the boundary, not just the happy path
Worked example · One pass
[5, 2, 4, 1] -> [2, 4, 1, 5]Adjacent swaps carry 5 to the end, establishing that the final position is sorted after the pass.
Worked example · Early exit
if no swaps occurred during a pass: stopNo adjacent inversion means the entire remaining range is ordered, making an optimized best case Theta(n).
Useful contrast · Large displacement
[n, 1, 2, ..., n-1]The leading maximum moves quickly right, but a small value can move left only one position per pass in the common forward variant.
Common mistakes
Misconceptions to remove early
Using it for large general-purpose sorts
Average and worst-case work are Theta(n^2). Standard library sorts provide far better guarantees and tuned implementations.
Swapping equal keys
Swapping when left >= right can reverse equal elements and lose stability. Swap only on a strict inversion when stability matters.
Quick check
Can you predict the result?
1. What is guaranteed after a complete left-to-right bubble-sort pass?
- • The largest element in the active range is at that range's right end
- • Every element is globally sorted
- • The smallest element is necessarily at the right end
2. How does a swap flag improve already sorted input?
Keep building