Bubble Sort moves one largest value to the end on every pass

Bubble Sort swaps only adjacent values that are out of order

Bubble Sort looks at two neighboring positions at a time. If the value at index j is greater than the value at index j + 1, those two values are out of order, so the algorithm swaps them. If they are already ordered, it leaves them alone. On [5, 1, 4(first), 2, 4(second)], the first comparison examines 5 and 1, so the array becomes [1, 5, 4(first), 2, 4(second)]. This repairs the inversion between those two positions, but it does not inspect the rest of the array or sort it immediately.

The next comparison starts at the new position of the value that moved right. Comparing 5 and 4(first) swaps them, giving [1, 4(first), 5, 2, 4(second)]. Comparing 5 and 2 swaps them again, giving [1, 4(first), 2, 5, 4(second)]. A final comparison of 5 and 4(second) gives [1, 4(first), 2, 4(second), 5]. Each swap repairs one adjacent inversion. Several repairs can move one value a long distance, but other values can still be out of order.

One left-to-right pass places the largest remaining value at its final index

A pass compares each adjacent pair from left to right. In the first pass, 5 is larger than every value to its right, so every swap involving 5 moves it one position right. The comparisons and results are [5, 1, 4(first), 2, 4(second)], then [1, 5, 4(first), 2, 4(second)], then [1, 4(first), 5, 2, 4(second)], then [1, 4(first), 2, 5, 4(second)], and finally [1, 4(first), 2, 4(second), 5].

The value 5 reaches index 4, so index 4 is now its final index. The prefix [1, 4(first), 2, 4(second)] is still unsorted because 4(first) is out of order with 2. This directly breaks the idea that one left-to-right pass sorts the entire array. One pass guarantees the correct position of the largest remaining value, not the correct position of every value.

The sorted suffix makes each later pass shorter

After the first pass, 5 is in its final index, so later passes do not need to compare it with anything. The second pass, numbered pass 1 when counting from zero, examines j = 0, j = 1, and j = 2. Starting with [1, 4(first), 2, 4(second), 5], the comparison at j = 0 leaves 1 and 4(first) unchanged. The comparison at j = 1 swaps 4(first) and 2, producing [1, 2, 4(first), 4(second), 5]. The comparison at j = 2 leaves 4(first) and 4(second) unchanged.

After pass 1, the final suffix is [4(second), 5] at indices 3 and 4. The active prefix has indices 0 through 2. For a zero-based pass number called pass, the inner loop can use j < n - 1 - pass. With n = 5, pass 0 gives j < 4, so j is 0 through 3. Pass 1 gives j < 3, so j is 0 through 2. Because the loop also reads j + 1, the largest j must be one less than the last index being considered. The bound both keeps j + 1 valid and excludes the final suffix.

for (int j = 0; j < ____; j++)

A pass with no swaps proves that the array is sorted

After the second pass, the array is [1, 2, 4(first), 4(second), 5]. The third pass, numbered pass 2, checks only the active prefix through j = 1. The comparison of 1 and 2 needs no swap, and the comparison of 2 and 4(first) needs no swap. The pass makes no swaps, while [4(first), 4(second), 5] is already a sorted suffix.

A no-swap pass is proof that the active prefix needs no repair. Every adjacent pair checked in that prefix is ordered, so no larger value is waiting to move right through it. Since the sorted suffix is already final, the entire array is sorted. An implementation can use an early break immediately after this unchanged pass instead of starting another pass.

Bubble Sort uses constant extra space but can make quadratically many comparisons

For the running array, the first executed pass makes 4 adjacent comparisons, the second makes 3, and the third makes 2 before the no-swap stop. If the early break never occurs, the comparison counts form a triangle: (n - 1) + (n - 2) + ... + 1. That sum grows proportionally to n squared, so the worst-case time complexity is O(n^2).

Bubble Sort changes the array in place. It needs only a few variables such as j and a temporary value for a swap, so its extra space complexity is O(1). When the input is already sorted, the first pass makes n - 1 comparisons, performs no swaps, and stops. The no-swap break therefore gives O(n) best-case time.

The comparison must be strict: swap only when the left value is greater than the right value. When 4(first) is compared with 4(second), the values are equal, so they are not swapped. Their original order remains 4(first) before 4(second). Preserving the order of equal values makes this Bubble Sort implementation stable.