Bubble Sort: One Adjacent Swap Moves a Value Along

Swapping an out-of-order adjacent pair moves the larger value one position right

Bubble Sort looks at neighboring values, not at every possible pair. For the array [8, 5, 1, 4, 2], the first adjacent pair is 8 and 5. Because 8 is greater than 5, the pair is out of order, so Bubble Sort swaps them. The array becomes [5, 8, 1, 4, 2]. The larger value, 8, has moved exactly one position right.

if (arr[j] > arr[j + 1]) {
    swap(arr[j], arr[j + 1]);
}

The comparison uses a strict greater-than test. If the left value is smaller, the pair stays as it is. If the values are equal, they also stay as they are. A single swap changes only the two positions being compared, so it cannot move 8 from index 0 to the final slot immediately. It can only move 8 from index 0 to index 1.

One complete pass fixes only the largest remaining value

A pass continues comparing adjacent pairs from left to right. After the first swap, the next pair is 8 and 1, so another swap produces [5, 1, 8, 4, 2]. Then 8 swaps with 4, producing [5, 1, 4, 8, 2]. Finally, 8 swaps with 2, producing [5, 1, 4, 2, 8]. The value 8 has traveled to the end because every value it met was smaller.

Start: [8, 5, 1, 4, 2]
8 and 5 -> [5, 8, 1, 4, 2]
8 and 1 -> [5, 1, 8, 4, 2]
8 and 4 -> [5, 1, 4, 8, 2]
8 and 2 -> [5, 1, 4, 2, 8]

The final position is now correct for 8, but the array is not sorted. The prefix begins with 5 followed by 1, which is still out of order. This breaks the idea that comparing every adjacent pair once sorts everything. One pass fixes only the largest remaining value, because that value keeps moving right whenever it is larger than its neighbor.

The sorted suffix makes each later pass shorter

After pass 1, 8 is a sorted suffix of one value. No later pass needs to compare anything with index 4, because no remaining value can belong after 8. Pass 2 therefore stops before index 4. It moves 5 through the remaining prefix and ends with [1, 4, 2, 5, 8]. Now 5 and 8 form a sorted suffix.

The boundary follows the rule j < n - 1 - pass when pass starts at 0. For n = 5, the first pass compares j values 0 through 3. The next pass compares 0 through 2, because index 4 is fixed. Each later pass ignores one more value at the right, so the sorted suffix grows while the unsorted prefix shrinks.

A pass with no swaps proves that no later pass is needed

After pass 3, the array is already [1, 2, 4, 5, 8]. The implementation still needs a way to prove that no useful change remains. On pass 4, the shrinking boundary leaves only the pair 1 and 2. Since 1 is not greater than 2, no swap happens. Every compared adjacent pair was already ordered, so the unsorted prefix cannot contain an inversion that a later pass could fix.

bool swapped = false;

for (int j = 0; j < n - 1 - pass; j++) {
    if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
        swapped = true;
    }
}

if (!swapped) {
    break;
}

The no-swap pass is different from merely seeing a sorted-looking array after pass 3. Pass 3 produces the sorted array, but it also performs a swap, so that pass does not by itself prove that the array was already ordered before it began. Pass 4 checks the remaining pair and makes no swap, which is the proof used by the early-stop condition.

Bubble Sort is quadratic in the worst case, in-place, and stable with strict swaps

For [8, 5, 1, 4, 2], the early-stop implementation performs 4 comparisons on pass 1, 3 on pass 2, 2 on pass 3, and 1 on pass 4, for 10 comparisons total. The swaps are 4, 3, 1, and 0, for 8 swaps total. Pass 4 is still useful even though it changes nothing, because its no-swap result allows the algorithm to stop.

In the worst case, the array keeps needing swaps until the shrinking prefix has only one value left. The comparison counts form 1 + 2 + ... + (n - 1), which grows as O(n^2). If the input is already sorted, the first pass makes no swaps and early stopping gives O(n) best-case time. Bubble Sort uses O(1) extra space because it rearranges values inside the original array.

The strict condition arr[j] > arr[j + 1] makes Bubble Sort stable. Equal values are never swapped with each other, so their original relative order is preserved. Replacing the condition with greater-than-or-equal would allow equal values to cross, removing that stability guarantee without improving the sorting result.