Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps out-of-order pairs, sweeping the largest remaining value to the end of the array on each pass. This stable, comparison-based sort has O(n²) average and worst-case time complexity; an early-exit check gives it an O(n) best case. It works in place with O(1) extra space.

Picture values trapped in a row where the only legal move is swapping neighbors. A large value can ride a left-to-right sweep all the way to the right, rising through the row like a bubble through water. A small value can move left only one position during that same pass. Put the minimum at the far right, as the classic default does with 7, and it takes all n - 1 passes to crawl home.

How Bubble Sort Works

Two nested loops. The outer loop counts passes, with i running from 0 through n - 2. The inner loop sweeps j from 0 through n - 2 - i, compares arr[j] with arr[j + 1], and swaps when the left value is larger.

The inner loop carries a proof as it moves. After resolving the comparison at j, arr[j + 1] is the largest value in arr[0..j + 1]. The max marker in the animation follows that running maximum: after a swap, it moves right with the value that started on the left; after a no-swap comparison, it transfers to the right value. By the final comparison, the maximum of the unsorted prefix has reached its last position.

That gives the outer-loop invariant: after pass i, the last i + 1 positions contain the i + 1 largest values, in order, in their final positions. The next pass stops one position earlier because the green suffix is settled. The divider on the canvas marks that shrinking boundary.

This lesson has two variants. Classic always runs all n - 1 passes. Optimized resets a swapped flag to false at the start of every pass and sets it to true whenever a swap occurs. If a full pass leaves the flag false, no adjacent pair is out of order, so the whole array is sorted. Until that check, both variants make the same adjacent comparisons and swaps; the flag only lets optimized bubble sort skip passes that are no longer needed.

Bubble Sort Step by Step

The default run uses the classic variant on [24, 38, 12, 45, 19, 31, 7]. The 7 starts at index 6. Since a value can move left only once per pass, 7 must survive six sweeps before it can reach index 0.

Pass 1 makes six comparisons. 24 ≤ 38, so the running maximum transfers to 38. Then 38 > 12 swaps. 38 ≤ 45 hands the maximum to 45, and 45 swaps past 19, 31, and 7. The pass makes four swaps and ends at [24, 12, 38, 19, 31, 7, 45]. The 45 is final at index 6; 7 has moved left once, to index 5.

Pass 2 makes five comparisons over the remaining prefix. 24 > 12 swaps, 24 ≤ 38 leaves the pair alone, then 38 swaps past 19, 31, and 7. The row becomes [12, 24, 19, 31, 7, 38, 45]. Now 38 is final at index 5, and the green suffix is [38, 45].

Passes 3 through 6 repeat the same argument, settling 31, 24, 19, and 12. The stranded 7 moves from index 4 to 3, then 2, 1, and finally 0. The result is [7, 12, 19, 24, 31, 38, 45]: six passes, 21 comparisons, and 13 swaps.

Switch to Optimized and the lesson loads [30, 12, 23, 47, 58, 76, 91], an input chosen to expose the early exit. Pass 1 swaps 30 past 12 and 23, producing [12, 23, 30, 47, 58, 76, 91]. Pass 2 checks the five remaining adjacent pairs and swaps nothing. The flag stays false, the whole row turns green, and the trace stops after 11 comparisons and 2 swaps. Passes 3 through 6 never run.

While a pass runs, the j and j + 1 pointers mark the pair under comparison, and the max tag follows the largest value seen so far. After a Classic pass, or an Optimized pass that swapped, one more cell joins the green suffix. If Optimized finishes a pass without swapping, the entire row turns green and the run stops.

Time and Space Complexity

Count comparisons separately from swaps. For an array of length n, Classic checks n - 1 pairs on pass 1, n - 2 on pass 2, and one fewer on each later pass:

(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2

For seven values, 6 + 5 + 4 + 3 + 2 + 1 gives 21 comparisons. The starting order cannot change that total; it changes only how many comparisons cause swaps.

The swapped flag matters at the end of a pass. On an already sorted array of length n, the first pass makes n - 1 comparisons, leaves the flag false, and ends the run in O(n) time. On the lesson's optimized default, pass 1 moves 30 behind 12 and 23; pass 2 makes five comparisons without a swap. The final count is 11 comparisons and 2 swaps.

Descending order leaves no chance to stop early because every comparison swaps. With seven values, both variants make 21 comparisons and 21 swaps. The optimized worst case is still O(n²).

Neither variant allocates another array. The temporary swap variable takes constant space, so extra space remains O(1). The strict > comparison preserves stability: equal neighbors keep their original order, while >= would allow them to cross.

Edge Cases

• One value: Single element loads [42]. There is no adjacent pair, so the trace initializes and finishes without entering a pass.
• Already sorted: [12, 23, 30, 47, 58, 76, 91] is the optimized best case. Six comparisons, no swaps, stop.
• Nearly sorted: [12, 23, 30, 47, 58, 91, 76] needs one swap on the first pass. No pair swaps on the next pass, so optimized stops after 11 comparisons instead of continuing through all six passes.
• Reversed: classic runs on [91, 76, 58, 47, 30, 23, 12]. Every one of its 21 comparisons triggers a swap.
• All equal: the five 42s never cross because the condition is >, not >=. Optimized sees four no-swap comparisons and exits.

Common Mistakes

The presets make the usual bugs easier to catch. Sorted input tests the early exit, reversed input stresses every comparison, and equal values test whether the swap condition is strict.

• Get both ends of the inner loop right. The code uses j < n - 1 - i, so the last comparison starts at j = n - 2 - i. Go one step farther and the first pass reads past the array; later passes compare into the settled suffix. Stop one step sooner and the pass may strand its maximum.
• Reset and inspect swapped at different times. Reset it inside the outer loop, before the sweep. Inspect it only after the sweep. A flag reset outside the loop can never recover from an earlier swap; a flag checked inside the loop mistakes one ordered pair for an ordered array.
• Do not damage the swap. Save the old left value before overwriting either cell if your language has no tuple assignment. And keep the test strict: >= sorts the numbers, but it throws away stability by moving equal keys past one another.
• Do not label optimized bubble sort O(n). That is its best case. Average and worst-case time remain O(n²), and the reversed preset demonstrates the latter without any algebra.