Compare each pair of neighbours and swap them if they are out of order. Watch the largest value ride to the end.
The largest value bubbles to the end
Ten numbers, neighbours compared and swapped
void bubble_sort(int *a, int n){ for (int end = n - 1; end > 0; end--) { bool swapped = false; for (int i = 0; i < end; i++) { comparisons++; if (a[i] > a[i + 1]) { int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; swaps++; swapped = true; } } if (!swapped) break; }}main has started: a has room for ten ints.
- pass
- –
- comparisons
- 0
- swaps
- 0
Output
Describe this picture
Ten bars in a row, the cells of int a[10], each as tall as its value: 6 2 9 1 5 10 3 8 4 7, with the cell numbers 0 to 9 above them. The code pane beside the picture shows bubble_sort, with the line about to run marked. The clip takes about 30 seconds. For each comparison, two neighbouring bars are tinted, with the marker i under the left one. When the left bar is taller, the two slide past each other. The first pass plays slowly: 10 rides all the way from cell 5 to cell 9, and its bar greys, sorted. Each later pass is quicker, and the grey tail at the right grows by one bar each time. The sixth pass compares 1 2 3 4 5 and swaps nothing, so the sort stops and every bar greys. Under the picture are one sentence on the current step and the readouts “pass”, “comparisons” and “swaps”, which end at 6, 39 and 20. The transport plays and pauses, steps one beat back or forward, and scrubs; a paused step is kept in the page address as bubble-sort.step.
Neighbours, swapped
Walk along the array comparing each value with the next one. If the left one is larger, swap them. The largest value is then swapped at every comparison it takes part in, so it is carried to the last cell: after one pass it is in its final place. The next pass can stop one cell earlier, and carries the second largest to the cell before the last. Each pass places one more value at the end.
Other values move too. In the first pass on 6 2 9 1 5 10 3 8 4 7, 2 swaps with 6, and 9 moves right until it meets 10. Every value with a larger value anywhere before it moves one place left. That is why a pass can find the array already sorted before the last pass is due.
The code and its cost
void bubble_sort(int *a, int n)
{
for (int end = n - 1; end > 0; end--) {
bool swapped = false;
for (int i = 0; i < end; i++) {
comparisons++;
if (a[i] > a[i + 1]) {
int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
swaps++;
swapped = true;
}
}
if (!swapped)
break;
}
}end is the last cell of the part not yet sorted. The inner loop compares a[i] with a[i + 1] for i from 0 to end − 1, and swaps a pair that is out of order through t. swapped records whether the pass changed anything. If it did not, every neighbouring pair is in order, so the whole array is, and the sort stops early.
Counting the work
A pass over the first end + 1 cells makes end comparisons. Without the early stop, the passes make 9 + 8 + … + 1 = 45 comparisons on ten values, and n(n − 1)/2 on n. On the house array, bubble.c stops after 6 passes: 9 + 8 + 7 + 6 + 5 + 4 = 39 comparisons. The first five passes swap; the sixth only confirms that nothing is out of order. It prints 39 comparisons, 20 swaps.
Swaps are inversions
An inversion is a pair of values in the wrong order: a larger one somewhere before a smaller one. The house array has 20 of them. A swap exchanges two neighbours that are in the wrong order, and changes no other pair’s order, so every swap removes exactly one inversion. The sort ends with none left, so it made exactly 20 swaps, whatever the order of its passes.
The number of passes has a reason too. A pass moves a value left by at most one place. 4 has five larger values before it (6, 9, 5, 10 and 8), so it needs five passes that swap before it reaches its place; then one more pass finds nothing to do.
Three properties for the whole chapter
Every sort in this chapter is judged on the same three questions.
- In place: it needs only a fixed amount of extra memory, here one
int t, whatever n is. - Stable: values that are equal keep their order. Bubble sort swaps only when
a[i] > a[i + 1], so two equal values are never swapped past each other. - Adaptive: it is faster on input that is nearly sorted. With the early stop, a sorted array costs one pass of n − 1 comparisons and no swaps.
The worst case is a reversed array: every pair is an inversion, n(n − 1)/2 of them, so it makes n(n − 1)/2 swaps and as many comparisons. That is O(n²), and the early stop does not change it. It helps only when the input is nearly sorted.
Worked example
The first pass. On 6 2 9 1 5 10 3 8 4 7, the first pass swaps 6 and 2, then 9 and 1, 9 and 5, then 10 with 3, 8, 4 and 7, giving 2 6 1 5 9 3 8 4 7 10. 10 is in its place.
Reversed and sorted. bubble-cases.c runs the same function on 10 9 8 … 1: 45 comparisons and 45 swaps, the worst case, since all 45 pairs are inversions. On 1 2 … 10 it makes 9 comparisons and no swaps: one pass, then the early stop.
Two checks. How many inversions does 3 1 2 have? (2: 3 before 1 and 3 before 2.) If the test were a[i] >= a[i + 1], would the sort still be stable? (No: two equal neighbours would be swapped.)
Where it’s used
Teaching. Bubble sort is the simplest sort to state and to check by hand, and its counts are a baseline: every other sort in this chapter makes fewer comparisons or fewer swaps on the same ten values, starting with Insertion sort.
Nearly sorted data. A single pass with the early stop confirms that an array is sorted in n − 1 comparisons, and fixes a few neighbours that are out of order.
Reference card
| Code or idea | Meaning |
|---|---|
| one pass | compare a[i], a[i + 1] for i below end; swap if out of order |
| after pass k | the k largest values are in their places at the end |
| early stop | a pass with no swap: the array is sorted |
| inversion | a pair in the wrong order; each swap removes one |
| comparisons | n(n − 1)/2 at worst, n − 1 on sorted input |
| swaps | the number of inversions |
| in place, stable, adaptive | yes, yes, yes |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.