Bubble Sort —
The simplest sort, and the clearest case for why O(n²) is slow.
Compare each pair of neighbors, swap them if they're out of order, and repeat until nothing swaps anymore. It's rarely the right choice in practice, but it's the clearest possible demonstration of what a nested loop actually costs. Watch every comparison and every swap happen on LearnBug and see the largest values "bubble" to the end, one pass at a time.
What is Bubble Sort?
Walk through the array comparing each adjacent pair; if the left one is bigger than the right one, swap them. One full pass guarantees the largest remaining element ends up at the very end. Repeat for n-1 passes total, and the array is sorted — each pass needs one fewer comparison, since the tail is already settled.
Why visualization helps
Bubble sort's whole value as a teaching tool is that you can watch the nested loop's cost directly — every single comparison is visible, not hidden behind an abstraction. LearnBug shows each swap decision and the largest value visibly "bubbling" toward its final position pass by pass, which is exactly what makes O(n²) feel real instead of theoretical.
Why it's called "bubble" sort
One pass moves the max to the end
Every adjacent swap moves the larger value one step to the right. By the end of a full left-to-right pass, the single largest element has "bubbled" all the way to the last position.
Each pass shrinks the unsorted region
After pass 1, the last element is settled. After pass 2, the last two are settled. The inner loop shrinks by one comparison every pass — no need to re-check already-sorted tail elements.
Early exit when nothing swaps
If a full pass makes zero swaps, the array is already sorted — an optional flag lets bubble sort stop early instead of running all n-1 passes unconditionally.
Sorting [5, 1, 4, 2, 8] — the first pass
Compare 5, 1 → 5 > 1, swap → [1, 5, 4, 2, 8]
Adjacent comparison at index 0/1. 5 is larger than 1 and to its left, so they're out of order — swap them.
Compare 5, 4 → swap → [1, 4, 5, 2, 8]. Compare 5, 2 → swap → [1, 4, 2, 5, 8]
The 5 that moved right in step 1 keeps getting compared to its new neighbor and keeps winning — it's "bubbling" rightward one position at a time through the whole pass.
Compare 5, 8 → already in order, no swap. Pass 1 complete: [1, 4, 2, 5, 8]
8 is the true maximum, so it stays put. Pass 1 ends with 8 correctly in its final position — the largest element of the whole array reached the end in exactly one pass.
Passes 2-4 repeat the same idea on a shrinking range, until sorted
Pass 2 settles the second-largest value (5) at index 3, ignoring the already-settled 8. This continues, each pass one comparison shorter than the last, until the whole array is sorted.
Return: [1, 2, 4, 5, 8] ✓ 4 passes for 5 elements, up to 4+3+2+1 = 10 comparisons worst case
Nested loop, adjacent swaps
arr = [5, 1, 4, 2, 8]
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - i - 1): # shrinks by 1 each pass — tail is already sorted
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j] # swap
print(arr)Complexity Notes
Frequently asked questions
Why does the inner loop range shrink each pass?
Every completed pass guarantees the current maximum of the remaining unsorted region has bubbled to its correct final position at the end of that region. Comparing against it again in future passes would be wasted work, so range(n - i - 1) stops one element earlier with every pass — this alone roughly halves the total comparisons compared to not shrinking the range.
How would I add the early-exit optimization?
Track a boolean flag, set it to False before each pass, and set it to True whenever a swap happens. If a full pass finishes with the flag still False, no swaps occurred — the array is already sorted — so you can break out of the outer loop immediately instead of running the remaining passes unnecessarily.
Is bubble sort ever actually the right choice?
Almost never in production — insertion sort dominates it on nearly every input (fewer writes, similar or better performance), and any O(n log n) algorithm dominates both for larger n. Bubble sort's real value today is purely educational: it's the clearest possible illustration of what a nested comparison loop costs.
Why is it considered a stable sort?
The swap condition is strictly arr[j] > arr[j+1] — two equal elements are never swapped, since neither is strictly greater than the other. That means equal elements can never cross each other during any pass, which is exactly the definition of a stable sort.
Watch the largest value bubble to the end, pass by pass
Paste bubble sort into LearnBug and see every comparison and every swap live.