Bubble Sort Step by Step
Repeatedly swapping neighbours that are out of order is the least efficient way to sort anything, and also the clearest window into what sorting actually is. Every pass drags the biggest remaining value to the end, which is why it is worth watching once: the mechanism is visible in a way that quicksort's partitioning never is.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
void bubbleSort(vector<int>& a) {
int n = a.size();
for (int pass = 0; pass < n - 1; pass++) {
bool swapped = false;
for (int i = 0; i < n - 1 - pass; i++) {
if (a[i] > a[i + 1]) {
int tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
swapped = true;
}
}
if (!swapped) break;
}
}
int main() {
vector<int> a = {5, 1, 4, 2, 8};
bubbleSort(a);
for (int x : a) cout << x << ' ';
return 0;
}The optimised version: the inner loop shrinks each pass, and the swapped flag exits early once a full pass makes no changes.
How it works, step by step
Only adjacent pairs are ever compared
The inner loop looks at a[i] and a[i+1] and nothing else. A value can therefore move at most one position per comparison, which is precisely why the algorithm is slow — an element at the front that belongs at the back needs n-1 separate swaps to get there.
Each pass parks one element permanently
Follow the largest value: once the scan reaches it, every subsequent comparison swaps it forward, so it rides to the end of the pass in one continuous sweep. After pass k, the last k positions hold the k largest values in final order.
That is why the inner loop shrinks
n - 1 - pass stops the scan before the already-sorted tail. Without it the algorithm still works but wastes a growing number of guaranteed-false comparisons on every pass.
The swapped flag detects sortedness
If an entire pass makes zero swaps, no adjacent pair is out of order, and an array with no out-of-order adjacent pairs is sorted. That turns the best case for nearly-sorted input from O(n squared) into a single O(n) verification pass.
Stability comes from the strict comparison
The swap only fires on a[i] > a[i+1], never on equality, so equal elements never cross each other. Change it to >= and you break stability while doing strictly more work.
Complexity
There are roughly n squared over 2 comparisons because each of n passes scans most of the array; the best case only reaches O(n) if you keep the swapped flag, and the worst case (a reversed array) forces every single swap.
Common bugs
Off-by-one at a[i + 1]
Writing for (int i = 0; i < n; i++) with a[i + 1] inside reads one element past the end on the last iteration. In C++ that is undefined behaviour and often appears to work — the vector has spare capacity and you read garbage that happens to be large. The bound must be n - 1 - pass.
Losing a value in a hand-written swap
a[i] = a[i+1]; a[i+1] = a[i]; overwrites a[i] before it is saved, so both slots end up holding the same value and the original is gone. Watching the array in a step-through makes it unmistakable: a duplicate appears and an element vanishes. Use a temporary, or std::swap.
Declaring swapped outside the outer loop
If bool swapped = false lives above the pass loop, it stays true forever after the first swap and the early exit never fires. Worse, some people set it true once and check it inverted, which exits after pass one and leaves the array half-sorted. It must be reset at the top of every pass.
int n = a.size() then looping to n - 1 on an empty vector
For an empty or single-element vector, n - 1 is 0 or -1 and the loops correctly do nothing — but only because n is a signed int. If you write a.size() - 1 directly in the condition, the unsigned wraparound produces a gigantic bound and the function walks off the end.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
Why is bubble sort so slow?
Because elements move only one position per swap. An element that needs to travel from the front to the back requires n-1 individual swaps, and with n elements potentially needing that, the total work is proportional to n squared. Algorithms like merge sort move elements large distances in a single step, which is the entire difference.
Is bubble sort ever actually used?
Almost never in production, but it has one genuine niche: detecting whether a nearly-sorted array is already in order. With the swapped-flag optimisation it confirms sortedness in a single O(n) pass and touches no memory beyond the array itself. Real libraries use insertion sort for that job instead, since it handles small disorder just as cheaply and degrades far better.
What is the difference between bubble sort and selection sort?
Bubble sort swaps adjacent out-of-order pairs repeatedly, so it performs many swaps but can stop early when the array is sorted. Selection sort scans for the minimum and performs exactly one swap per pass, so it does far fewer writes but always runs the full n squared comparisons regardless of the input.
Is bubble sort stable?
Yes, as long as the comparison is strictly greater-than. Equal elements are never swapped past each other, so their original relative order survives. Changing the condition to >= makes it unstable and adds pointless swaps.