Bubble sort, one swap at a time
Type up to twelve numbers. Each pass compares neighbours, swaps any pair in the wrong order, and floats the largest to the top.
0 passes
0 comparisons
0 swaps
Ready. The bottom of the column is the start of the list.
Neighbours trade places
Bubble sort only ever looks at two items side by side. If the lower one is bigger, they swap. Walk the whole list like that and the biggest item ends up at the top. Walk it again, one step shorter each time, until a pass goes by with no swaps at all.
function bubbleSort(list: number[]): number[] {
const a = [...list];
for (let pass = 0; pass < a.length - 1; pass++) {
let swapped = false;
for (let j = 0; j < a.length - 1 - pass; j++) {
if (a[j] > a[j + 1]) {
[a[j], a[j + 1]] = [a[j + 1], a[j]];
swapped = true;
}
}
if (!swapped) break; // nothing moved: already sorted
}
return a;
}Compare
Take the first two items. Is the lower one bigger than the one above it?
Swap
If it is, exchange them. The bigger item moves up one place and is compared again.
Settle
After each pass the largest unsorted item is at the top, and the next pass stops below it.
Sorting 5 1 4 2 8 by hand
| Pass | Before | After | Comparisons | Swaps | What happened |
|---|---|---|---|---|---|
| 1 | 5 1 4 2 8 | 1 4 2 5 8 | 4 | 3 | 5 rises past 1, 4 and 2, then stops under 8. 8 is in place. |
| 2 | 1 4 2 5 8 | 1 2 4 5 8 | 3 | 1 | 4 rises past 2. 5 is in place. |
| 3 | 1 2 4 5 8 | 1 2 4 5 8 | 2 | 0 | Nothing moves, so the list is sorted. Stop. |
| Total | 9 | 4 | Three passes, and the third only proves the list is done. |
4,950
comparisons to sort 100 items that start in reverse order: n × (n − 1) ÷ 2. Double the list and the work goes up four times.
What it costs
Fine for a handful of numbers, slow for a warehouse of them. When the list is already in order, one pass with no swaps settles it: 99 comparisons for 100 items.
45
comparisons at most for ten items, like the column above
499,500
comparisons for 1,000 items
Why it is called bubble sort
Large values drift up through the list the way bubbles rise through a glass: each pass lifts one more to the surface, and it stays there.
Named in 1962, used since 1956
Sorting by exchange
Edward Friend described the method in 1956, in “Sorting on Electronic Computer Systems”, when lists lived on punched cards and magnetic tape and every pass meant reading the tape again.
A catchy name
Kenneth Iverson used the name bubble sort in 1962. Donald Knuth later wrote that it “seems to have nothing to recommend it, except a catchy name”. It is still the first sort most people learn.
