Bubble sort [1,3,2,4] ascending with early-exit. Passes and swaps?[1, 3, 2, 4] — one out-of-order adjacent pair at positions 1 and 2
Example 3
medium
Bubble sort [5,1,4,2,8] ascending. Final list and total swap count?Initial state before ascending bubble sort of [5, 1, 4, 2, 8]
Example 4
hard
Trace bubble sort with early-exit on [3,2,1,4]. Give passes, swaps per pass, and total work.[3, 2, 1, 4] — trace bubble sort with early-exit from this state
Example 5
hard
Bubble sort [5,4,3,2,1] descending (largest first). Final list and swap count?[5, 4, 3, 2, 1] already sorted descending — zero swaps needed
Example 6
hard
Write pseudocode for bubble sort with both optimizations: early-exit and skip-last-k.
Example 7
challenge
Cocktail (bidirectional bubble) sort alternates left-to-right and right-to-left passes. On [5,1,4,2,8,0], does it finish faster than standard bubble sort? Sketch the argument.
Practice Problems
Try each one, then open the solution to compare your method.
Example 1
easy
What is bubble sort's time complexity?
Example 2
easy
Bubble sort compares which elements?
Example 3
easy
After one full pass of ascending bubble sort, which element reaches its correct final position?
Example 4
easy
Do one pass of ascending bubble sort on [3,1,2].Start of one ascending bubble-sort pass on [3, 1, 2]
Example 5
easy
If a bubble sort pass makes zero swaps, what does that tell you?
Example 6
easy
Bubble sort's best case (already sorted, with early exit) is what complexity?
Example 7
easy
How many adjacent comparisons does the FIRST pass make on a list of 5?
Example 8
easy
After k passes, why can you skip comparing the last k elements?
Example 9
medium
Fully bubble sort [2,4,1] (ascending). Give the final list and total number of swaps.Initial state before fully sorting [2, 4, 1] ascending
Example 10
medium
How many comparisons does unoptimized bubble sort make on a list of 4 (sum over all passes)?
Example 11
medium
On a reverse-sorted list [3,2,1], how many swaps does bubble sort make in total?Reverse-sorted [3, 2, 1] — bubble sort starts here
Example 12
medium
Why is bubble sort a poor choice for sorting a million records?
Example 13
medium
Without the last-k optimization, bubble sort compares into the already-sorted tail. What does this waste?
Example 14
medium
Is bubble sort stable, and what makes it so?
Example 15
medium
Bubble sort [1,2,3,5,4] with early exit. How many passes until it stops?[1, 2, 3, 5, 4] — only one out-of-order adjacent pair
Example 16
medium
Fully bubble sort [3,1,2] ascending. Give the final list and total swaps.Initial array [3, 1, 2] before full ascending bubble sort
Example 17
medium
How many comparisons does unoptimized bubble sort do on a list of 5 (sum over all passes)?
Example 18
challenge
Prove bubble sort's worst case does 2n(n−1) comparisons. Tie it to the number of inversions.
Example 19
challenge
Compare bubble sort and merge sort on (a) already-sorted and (b) reverse-sorted input of size n, in Big-O. When might bubble sort actually be preferable?
Example 20
challenge
A list has exactly 2 inversions. How many swaps will bubble sort make, and why does swap count equal inversion count?
Example 21
easy
Do one pass of ascending bubble sort on [5,2,4].Start of one ascending bubble-sort pass on [5, 2, 4]
Example 22
easy
On a list of 6 elements, how many adjacent comparisons does the first pass make?
Example 23
easy
True or false: bubble sort is a STABLE sorting algorithm.
Example 24
easy
After two complete passes of ascending bubble sort, which positions are guaranteed sorted?
Example 25
easy
Sort [2,1] with bubble sort. Number of swaps?[2, 1] — one comparison, one swap needed
Example 26
easy
How does bubble sort decide whether to swap two adjacent elements?
Example 27
easy
On a list of 7, how many adjacent comparisons does the FIRST pass make?
Example 28
medium
How many comparisons does unoptimized bubble sort make on a list of 6 (sum over passes)?
Example 29
medium
On reverse-sorted [4,3,2,1], how many bubble sort swaps total?Reverse-sorted [4, 3, 2, 1] — worst case for bubble sort
Example 30
medium
Why does early-exit optimization make sorted input O(n)?
Example 31
medium
Compare bubble sort and merge sort on n=10,000. Approximate ratio of comparisons.
Example 32
medium
After k passes of bubble sort on n items, what range still needs comparing in the next pass?
Example 33
medium
How many comparisons does unoptimized bubble sort do on n=10?
Example 34
medium
Without the skip-last-k optimization, what is wasted on later passes?
Example 35
medium
Why might bubble sort still be taught despite being slow?
Example 36
medium
An array [2,2,1] is sorted with bubble sort. After sorting, do the two 2's keep their original relative order? Why or why not?[2, 2, 1] — do the two equal 2's keep their relative order after sorting?
Example 37
hard
Why does bubble-sort swap count equal the inversion count of the input?
Example 38
hard
A list of 1 million records takes ~1s with merge sort. Roughly how long with bubble sort, assuming same per-op cost?
Example 39
hard
On a list where every element is one position away from its sorted spot, how many swaps does bubble sort make?
Example 40
hard
Bubble sort is sometimes called 'sinking sort' if implemented differently. What does the alternate variant do?
Example 41
challenge
Prove that bubble sort's worst-case swap count is exactly n(n−1)/2.
What to focus on
Core idea:Each pass moves the largest unsorted element to its correct position at the end.
Common stuck point:Bubble sort is O(n²) — avoid it for large data; use merge sort or quick sort instead.
Ask yourself:Is a list sorted by repeatedly swapping adjacent items that are out of order?
Concept recap
A simple sorting algorithm that repeatedly walks through the list, compares each pair of adjacent elements, and swaps them if they are in the wrong order. This process repeats until no more swaps are needed, meaning the list is fully sorted.
Bubble sort is like tidying books by height on a shelf when you may only swap two neighboring books. Walking left to right, you swap whenever a taller book stands left of a shorter one, so the tallest book is carried to the right end in a single sweep. A short book stuck at the far right moves only one place per sweep, which is why the method is slow.