DSA SheetLesson · no judge

SORTING › BUBBLE SORT / INSERTION SORT / SELECTION SORT

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

Reading · 6 minQuiz · 5 questions2 code drills · run onlyGenerated by gpt-5.6-luna · Aug 25

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.

CHECKPOINT 1Not answered

In the initial array [5, 1, 4(first), 2, 4(second)], which pair does Bubble Sort examine when j points to 4(first), and what does it do?

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

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 first Bubble Sort pass through [5, 1, 4, 2, 4]Five rows trace the first pass. The starting row is [5, 1, 4(first), 2, 4(second)]. Swapping the highlighted adjacent pair at j = 0 gives [1, 5, 4(first), 2, 4(second)], at j = 1 gives [1, 4(first), 5, 2, 4(second)], at j = 2 gives [1, 4(first), 2, 5, 4(second)], and at j = 3 gives [1, 4(first), 2, 4(second), 5]. Index 4 is marked final, while the prefix [1, 4(first), 2, 4(second)] is marked active and still unsorted.514₁24₂154₁24₂14₁524₂14₁254₂14₁24₂5swapswapswapswapEach adjacent swap moves 5 right; only index 4 is final.01234j = 0j = 1j = 2j = 3index 4 finalindices 0–3 remain unsorted
A pass fixes the largest remaining value, not the whole array.

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.

CHECKPOINT 2Not answered

Complete the inner-loop condition for pass on n = 5: for (int j = 0; j < ____; j++)

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

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

The shrinking active prefix of [5, 1, 4, 2, 4] across its passesThree aligned rows show shorter comparison ranges. Pass 0 uses j = 0-3 and ends at [1, 4(first), 2, 4(second), 5], with 5 in the final suffix. Pass 1 uses j = 0-2 and ends at [1, 2, 4(first), 4(second), 5], with 4(second) and 5 in the final suffix. Pass 2 uses j = 0-1, makes no swaps, and stops. The formula j < n - 1 - pass appears beside the ranges.14 (first)24 (second)5124 (first)4 (second)5124 (first)4 (second)501234Pass 0j = 0–3Pass 1j = 0–2Pass 2j = 0–1j < n − 1 − passj < 4j < n − 1 − passj < 3j < n − 1 − passj < 2no swaps → stopEach pass adds one final position; the next comparison range is shorter.final suffix
The final suffix grows as the comparison range shrinks.

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.

Next part · Quiz