Bubble Sort
Compare neighbours. Swap the ones out of order. The largest value bubbles to the right each pass.
Sort 7 values. Each pass bubbles the largest remaining value to the right.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 18, with their answers.
Next pair: 5 and 1. What happens?
Answer: Swap. 5 > 1, so they swap.
Next pair: 5 and 4. What happens?
Answer: Swap. 5 > 4, so they swap.
Next pair: 5 and 2. What happens?
Answer: Swap. 5 > 2, so they swap.
Next pair: 5 and 8. What happens?
Answer: Keep. 5 <= 8, so they stay where they are.
Next pair: 8 and 3. What happens?
Answer: Swap. 8 > 3, so they swap.
Next pair: 8 and 7. What happens?
Answer: Swap. 8 > 7, so they swap.
Next pair: 1 and 4. What happens?
Answer: Keep. 1 <= 4, so they stay where they are.
Next pair: 4 and 2. What happens?
Answer: Swap. 4 > 2, so they swap.
Next pair: 4 and 5. What happens?
Answer: Keep. 4 <= 5, so they stay where they are.
Next pair: 5 and 3. What happens?
Answer: Swap. 5 > 3, so they swap.
Next pair: 5 and 7. What happens?
Answer: Keep. 5 <= 7, so they stay where they are.
Next pair: 1 and 2. What happens?
Answer: Keep. 1 <= 2, so they stay where they are.
Next pair: 2 and 4. What happens?
Answer: Keep. 2 <= 4, so they stay where they are.
Next pair: 4 and 3. What happens?
Answer: Swap. 4 > 3, so they swap.
Next pair: 4 and 5. What happens?
Answer: Keep. 4 <= 5, so they stay where they are.
Next pair: 1 and 2. What happens?
Answer: Keep. 1 <= 2, so they stay where they are.
Next pair: 2 and 3. What happens?
Answer: Keep. 2 <= 3, so they stay where they are.
Next pair: 3 and 4. What happens?
Answer: Keep. 3 <= 4, so they stay where they are.
How it runs, step by step
Sort 7 values. Each pass bubbles the largest remaining value to the right.
Bubble sort on 5, 1, 4, 2, 8, 3, 7. Adjacent pairs are compared left to right and swapped when out of order.
5 is larger than 1, so they swap.
Comparing 5 at index 0 with 1 at index 1. 5 is larger, so they swap places.
5 is larger than 4, so they swap.
Comparing 5 at index 1 with 4 at index 2. 5 is larger, so they swap places.
5 is larger than 2, so they swap.
Comparing 5 at index 2 with 2 at index 3. 5 is larger, so they swap places.
5 is not larger than 8, so they stay.
Comparing 5 at index 3 with 8 at index 4. They are in order, so nothing moves.
8 is larger than 3, so they swap.
Comparing 8 at index 4 with 3 at index 5. 8 is larger, so they swap places.
8 is larger than 7, so they swap.
Comparing 8 at index 5 with 7 at index 6. 8 is larger, so they swap places.
Pass 1 done: 8 is the largest of the unsorted part and settles at index 6.
Pass 1 complete. 8 settles at index 6. Sorted so far: 1 of 7.
1 is not larger than 4, so they stay.
Comparing 1 at index 0 with 4 at index 1. They are in order, so nothing moves.
4 is larger than 2, so they swap.
Comparing 4 at index 1 with 2 at index 2. 4 is larger, so they swap places.
4 is not larger than 5, so they stay.
Comparing 4 at index 2 with 5 at index 3. They are in order, so nothing moves.
5 is larger than 3, so they swap.
Comparing 5 at index 3 with 3 at index 4. 5 is larger, so they swap places.
5 is not larger than 7, so they stay.
Comparing 5 at index 4 with 7 at index 5. They are in order, so nothing moves.
Pass 2 done: 7 is the largest of the unsorted part and settles at index 5.
Pass 2 complete. 7 settles at index 5. Sorted so far: 2 of 7.
1 is not larger than 2, so they stay.
Comparing 1 at index 0 with 2 at index 1. They are in order, so nothing moves.
2 is not larger than 4, so they stay.
Comparing 2 at index 1 with 4 at index 2. They are in order, so nothing moves.
4 is larger than 3, so they swap.
Comparing 4 at index 2 with 3 at index 3. 4 is larger, so they swap places.
4 is not larger than 5, so they stay.
Comparing 4 at index 3 with 5 at index 4. They are in order, so nothing moves.
Pass 3 done: 5 is the largest of the unsorted part and settles at index 4.
Pass 3 complete. 5 settles at index 4. Sorted so far: 3 of 7.
1 is not larger than 2, so they stay.
Comparing 1 at index 0 with 2 at index 1. They are in order, so nothing moves.
2 is not larger than 3, so they stay.
Comparing 2 at index 1 with 3 at index 2. They are in order, so nothing moves.
3 is not larger than 4, so they stay.
Comparing 3 at index 2 with 4 at index 3. They are in order, so nothing moves.
No swaps in this pass, so everything is already in order. Stop early.
Pass 4 made no swaps. The array is sorted; the remaining passes are skipped.
Sorted. 18 comparisons and 8 swaps.
Result: the array is sorted in ascending order after 18 comparisons and 8 swaps.
Write it yourself
Define bubbleSort(values) and return the same values in ascending order. It runs in your browser against this lesson's own 5 examples.
// Walk the array, swapping neighbours that are out of order, until a pass makes no swap.function bubbleSort(values) { return values;}
Remember
- Each pass settles one more value on the right.
- A pass with no swaps means the array is already sorted.
- Stable and in place, but O(n^2). Fine for tiny inputs and hopeless for large ones.
Topics covered
Related
Where this is used
HardwareOdd-even transposition sort in hardware
Run bubble sort's compare-and-swap on every even-indexed pair at once, then every odd-indexed pair, and you have a sorting network that finishes in n rounds. FPGA and systolic-array sorters use it because each comparison touches only neighbouring cells, so the chip needs short local wires rather than a routing fabric. The asymptotically faster sorts lose here for the same reason they win in software: they compare elements that are far apart.
StatisticsKendall tau, the bubble sort distance
The number of adjacent swaps bubble sort makes is exactly the number of inversions between the input and sorted order, and that count is the Kendall tau distance between two rankings. Search and recommendation teams use it to measure how violently a new ranking model reshuffles results against the old one. Here the algorithm serves as a definition as much as a procedure.
GraphicsDepth sorting between frames
Transparent sprites and particles have to be drawn back to front, the painter's algorithm, and the camera usually moves only slightly between frames, so last frame's order is almost right. A pass or two of bubble or cocktail sort repairs the few pairs that flipped, and the early exit ends the sort as soon as a pass comes back clean. Each pass is one linear scan with no recursion and no allocation, which fits a fixed per-frame budget better than rebuilding the whole order with a fresh O(n log n) sort every frame.
EmbeddedMedian filters on microcontrollers
Smoothing a noisy sensor on an Arduino-class board usually means sorting five or nine samples and taking the middle one. Bubble sort is a common pick there for code size rather than speed: a handful of instructions, no recursion, no stack growth, and it sorts the sample window in place. At nine elements the O(n^2) never becomes visible.
Why it works this way
Why the inner loop stops at size - 1 - pass
After pass p the last p values are already in their final places, so rescanning them buys nothing. The bound is also what keeps a[j + 1] inside the array: stopping at a.size - pass instead reads one slot past the end. Dropping the - pass still sorts correctly, it just does roughly twice the comparisons.
The swapped flag does not make bubble sort fast
A value never moves left by more than one position per pass, so the early exit cannot fire until the furthest-travelling small value has finished crawling. A minimum sitting at the far right therefore forces n - 1 passes on its own, however sorted the rest is. Large values at the front are the opposite: one pass carries one of them all the way over. These are the turtles and the rabbits, and cocktail shaker sort alternates direction to give the turtles a fast lane.
Why the comparison is > and not >=
Equal neighbours are left alone, so two equal values can never cross each other and the sort stays stable. Using >= swaps them, which breaks stability and does work for no gain. It also kills the early exit: an array of identical values would set swapped on every comparison and grind through all n - 1 passes.
Where the n squared actually comes from
The passes cost n-1, n-2, down to 1 comparisons, and that sum is n(n-1)/2. The shrinking inner loop halves the constant and changes nothing about the growth. The swap count is sharper than the comparison count: bubble sort performs exactly one swap per inversion in the input, so a reversed array pays the full n(n-1)/2 and a nearly sorted one pays a handful.
Read more
- Bubble sortWikipedia
- Bubble sort: an archaeological algorithmic analysisOwen Astrachan, Duke University · users.cs.duke.edu
- Cocktail shaker sortWikipedia
- Odd-even sortWikipedia
- Kendall tau distanceWikipedia