Bubble Sort: Swapping Neighbours Until Nothing Moves

Each pass carries the largest remaining item to the end, one swap at a time.

Bubble sort orders an array by comparing each pair of neighbours and swapping them when they are out of order, so every pass carries the largest unsorted item to the end of the array. This card traces one run, explains the early exit that lets it stop on sorted input, and gives its costs.

A pass walks an index j from the start of the unsorted part, comparing the item at j with the item at j + 1 and swapping them when the left one is larger. The largest unsorted item wins every comparison it takes part in, so it rides all the way to the right end, where it joins the sorted part, and the next pass can stop one place earlier. After at most n − 1 passes every item is in place. The trace sorts 6 2 9 4 1 7 3. Each frame shows the array after one pass, with j and j+1 on the last pair that pass compared.

Bubble sort on seven numbers, one frame per pass

Input6 2 9 4 1 7 3, indices 0 to 6

After pass 1
1. 2
2. 6
3. 4
4. 1
5. 7
6. 3j
7. 9j+1
9 is carried right one swap at a time, five swaps in all, and ends the pass at index 6, where it stays.
After pass 2
1. 2
2. 4
3. 1
4. 6
5. 3j
6. 7j+1
7. 9
Three swaps carry 6 two places right and 7 to index 5, the second place from the end.
After pass 3
1. 2
2. 1
3. 4
4. 3j
5. 6j+1
6. 7
7. 9
4 swaps past 1 and 6 past 3, so 6 settles at index 4.
After pass 4
1. 1
2. 2
3. 3j
4. 4j+1
5. 6
6. 7
7. 9
2 swaps past 1 and 4 past 3. Every item is now in place, but the sort cannot know that yet.
After pass 5
1. 1
2. 2j
3. 3j+1
4. 4
5. 6
6. 7
7. 9
The pass compares 1 with 2 and 2 with 3 and swaps nothing, so the sort stops and skips pass 6.

ResultSorted after 5 passes: 20 comparisons, 12 swaps

The fifth pass swapped nothing, and that is the early exit: if no pair was out of order, the array is sorted, so the sort stops. Pass 4 had already sorted the array, but a pass that still made swaps cannot prove it, so one more pass has to see nothing move. On input that is already sorted the first pass swaps nothing, and the sort ends after n − 1 comparisons, its O(n) best case. On reversed input every comparison swaps, and the sort makes n(n − 1)/2 of each.

Each swap puts exactly one pair of items into the right order, and such an out-of-order pair is called an inversion. That is why the run made 12 swaps: 6 2 9 4 1 7 3 holds 12 inversions, counted pair by pair. Swapping only neighbours that are strictly out of order also makes bubble sort stable, because two equal items are never swapped and so never pass each other. A version that swaps when the left item is larger or equal still sorts, but it trades equal neighbours and loses that guarantee.

The costs, for an array of n items, are these.

Bubble sort on an array of n items

Best case: O(n); sorted input, with the early exit
Average case: O(n²); about n²/4 swaps on shuffled input
Worst case: O(n²); reversed input
Extra space: O(1); swaps inside the array
Stable: Yes; swaps only neighbours strictly out of order

Bubble sort is rarely the right choice for real data: it makes the same number of swaps as insertion sort, and each swap moves an item only one place. Its cues are teaching, and a single pass with no swaps as a cheap O(n) check that data is already sorted. What it makes visible is worth keeping: a sort is finished when no pair is out of order, and counting the inversions tells you how many swaps it will make before you run it.

On the Algorithms: Searching and Simple Sorting cheatsheet

← → move through sections and cards