Bubble Sort: one step at a time

Sorting and Searching · 25 min

Sorting · start from zero

Bubble Sort,
one step at a time.

The idea, one sweep traced by hand, the code, a demo you control step by step, and the interview questions that actually come up in placements. Nothing plays on its own — you press Next.

Run the sorting simulation →
A messy list
→
Sorted, small → large

01 The idea

What bubble sort does

Sorting means putting numbers in order, smallest to largest. Bubble sort does it the simplest way you can imagine: it only ever looks at two numbers standing next to each other.

Look at two neighbours. If the left one is bigger, swap them. Keep sweeping left to right, and the biggest value floats to the end — like a bubble rising in water. Repeat until a sweep makes no swaps.
ArrayA row of boxes holding our numbers, read left to right.
IndexThe position of a box. Counting starts at 0, not 1.
SwapTrading two numbers' places so the smaller one ends up on the left.

02 See one sweep

Watch the biggest number rise

One left-to-right sweep across 5 1 4 2. Follow the 5 — it keeps getting carried right until it lands at the end.

compare 5,151425 > 1 → swap
compare 5,415425 > 4 → swap
compare 5,214525 > 2 → swap
result14255 is home

Three comparisons moved the 5 into its final spot. Notice two things, because the next section turns both into one line of code each: the last box is now settled and never needs checking again, and if a sweep had made no swaps at all, the list was already in order.

03 The code

Naive first, then two small fixes

The naive version keeps sweeping the whole list every time. The optimised version adds two tiny changes, and both came straight from what you just saw by hand.

Naive

for (i = 0; i < n-1; i++)  for (j = 0; j < n-1; j++)    if (a[j] > a[j+1])      swap(a[j], a[j+1]);

Optimised

for (i = 0; i < n-1; i++) {  swapped = false;  for (j = 0; j < n-1-i; j++)    if (a[j] > a[j+1]) {      swap(a[j], a[j+1]);      swapped = true; }  if (!swapped) break;}

Fix 1 — j < n-1-i: the trace showed the tail is already settled after each sweep, so the inner loop should stop earlier every time instead of re-checking boxes that are done.

Fix 2 — the swapped flag: if a whole sweep makes no swaps, nothing was out of order, so break. This is what makes an already-sorted list finish in a single pass.

05 Cheat sheet

The numbers to remember

CaseTimeWhen
BestO(n)Already sorted — one sweep, no swaps, break
AverageO(n²)Random order
WorstO(n²)Reversed list
SpaceO(1)In place — one temp variable
StableEqual values keep their original order, because the swap fires only on strictly greater.
AdaptiveFaster on nearly-sorted data, thanks to the swapped flag. Only the optimised version.
In-placeNo extra arrays — it sorts inside the original list.

06 Where & why

When to actually use bubble sort

Be honest in an interview: bubble sort is almost never the fastest choice. Its value is being simple, stable, and in-place, so it earns a place only when that trade-off is worth it. Knowing when not to use something is most of what an interviewer is checking.

Reach for it when…

You are learning or teachingIt is the clearest way to watch comparisons and swaps happen, which is exactly why this lesson uses it.
The list is tinyFor a handful of items the O(n²) never bites, and short, obviously-correct code wins over clever code.
You just need a "sorted?" checkThe optimised version confirms an already-sorted list in one O(n) pass and stops.
The data is nearly sortedThe swapped flag lets it finish in very few passes when only a couple of items are out of place.
Memory and code space are tightIn-place, O(1) extra memory, no recursion stack, and few enough lines to audit by eye on embedded targets.

Use something else when…

SituationBetter choiceWhy
Large datasetQuicksort / Merge sortO(n log n) instead of O(n²) — the gap explodes as n grows
Guaranteed worst case neededMerge sort / Heap sortAlways O(n log n); quicksort can degrade to O(n²)
Large but nearly sortedInsertion sort / TimsortFewer moves, still simple; Timsort is built for exactly this
Big data, tight memoryHeap sortO(n log n) time with O(1) extra space
Real production codeThe built-in sortTimsort and introsort are tuned and battle-tested
In real projects you will almost always call the built-in sort. Bubble sort is for understanding how sorting works — and that understanding is what interviews are really testing.

07 Interview questions

What placements actually ask

The conceptual questions that come up in coding rounds and vivas. Tap a question to see a crisp answer — each one is short enough to say out loud in about twenty seconds.

How does bubble sort work, in one line?
Repeatedly compare adjacent pairs and swap the ones out of order. After each sweep the largest unsorted value has bubbled to its correct place. Repeat until a sweep makes no swaps.
What is its time complexity — best, average, worst?
Best is O(n) — an already-sorted list finishes in one sweep, but only with the swapped-flag optimisation. Average and worst are O(n²), and the worst case is a reverse-sorted list.
Why is the best case O(n) and not O(n²)?
Only because of the swapped flag. If a full sweep does zero swaps, the list is already sorted and we break out after n-1 comparisons. Remove the flag and every case becomes O(n²).
What is the space complexity?
O(1). It sorts in place using a single temporary variable to perform swaps — no extra arrays and no recursion stack.
Is bubble sort stable?
Yes. The swap fires only on strictly greater, a[j] > a[j+1], so two equal values never cross and keep their original order. Changing that to >= would break stability.
Is it adaptive?
Yes, in the optimised form. On nearly-sorted data the swapped flag lets it stop early, so it runs far closer to its best case than its worst. The naive version is not adaptive at all.
How many comparisons and swaps in the worst case?
Comparisons are n(n-1)/2. Worst-case swaps are also n(n-1)/2, on a fully reversed list. More usefully: the number of swaps always equals the number of inversions in the array.
Bubble vs selection vs insertion sort?
All three are O(n²). Bubble and insertion are stable and adaptive; selection is neither in its typical form. Selection does the fewest swaps at n-1, while insertion is usually the fastest of the three on nearly-sorted data.
What is the key optimisation to mention?
Two things, and mention both. Shrink the inner loop each sweep with j < n-1-i to skip the already-sorted tail, and add the swapped flag to break early when nothing moved.
When would you actually use it?
Almost never in production — only for tiny inputs, nearly-sorted data, or teaching. For real workloads use merge sort, quicksort, heapsort, or the language built-in. Saying this plainly is the right answer.

08 Practice problems

Same idea, with a twist

Each of these is solvable with the bubble sort idea, but bends it slightly — exactly the kind of variation interviewers use to check real understanding. Try them, then reveal the hint.

Count the swaps

Easy
Return how many swaps optimised bubble sort makes while sorting the array. Do not print the sorted list — just the count.
Follow-up
That count is exactly the number of inversions in the array, which is a different question wearing a disguise.
Show the hint
Increment a counter inside the if-swap block and return it after both loops finish.

Sort descending and stay stable

Easy
Sort the array largest-to-smallest while keeping equal elements in their original relative order.
Follow-up
Flipping the comparison is easy; keeping it strict is the part people get wrong and lose stability.
Show the hint
Swap on a[j] < a[j+1] and never on equality.

Array after K sweeps

Medium
Given an array and a number K, return the array after exactly K sweeps of bubble sort — not fully sorted.
Follow-up
You have to stop mid-algorithm, which tests whether you actually know what one sweep does.
Show the hint
Run the outer loop only K times, breaking early if a sweep makes no swaps.

Number of passes to sort

Medium
Return how many sweeps the optimised version needs before it stops on a given array.
Follow-up
Nearly-sorted inputs stop early, so you must count outer iterations rather than comparisons.
Show the hint
Count outer-loop turns until swapped stays false at the end of a sweep.

One swap to sort?

Medium
Return true if the array can be made fully sorted by swapping at most one pair of elements — any two, not just neighbours.
Follow-up
This is about positions out of place, not the bubble mechanics, so the loop structure will not help you.
Show the hint
Compare against a sorted copy; the number of mismatched positions must be 0 or exactly 2.

Minimum adjacent swaps

Hard
Return the minimum number of adjacent swaps needed to sort the array.
Follow-up
Bubble sort swap count is already optimal for adjacent swaps, so the brute force is the algorithm you just learned — the challenge is beating it.
Show the hint
Count inversions: O(n²) brute force, or O(n log n) with a merge-sort based count.