Bubble sort visualization

Bubble sort is a simple sorting algorithm that repeatedly compares neighboring elements and swaps them when they are in the wrong order. After one full pass the largest value has "bubbled" to the right end of the array, and further passes place the next largest values the same way.

How it works

1. Compare each pair of neighbors from left to right. If the left one is greater, swap them.
2. After the pass, the largest unsorted value is in its final place at the end.
3. Repeat the pass over the remaining unsorted part, which is one element shorter each time.
4. Stop when a whole pass makes no swap, or when only one element is left.

The early exit

If a whole pass swaps nothing, every neighboring pair is already in order, so the array is sorted and the algorithm stops. That is what makes the best case fast.

A worked example of bubble sort

Sort [5, 2, 4, 1, 3, 6]. The list shows the array after each pass:

1. [2, 4, 1, 3, 5, 6] with 5 comparisons and 4 swaps.
2. [2, 1, 3, 4, 5, 6] with 4 comparisons and 2 swaps.
3. [1, 2, 3, 4, 5, 6] with 3 comparisons and 1 swap.
4. [1, 2, 3, 4, 5, 6] with 2 comparisons and 0 swaps. No swap, so it stops.

In total: 14 comparisons and 7 swaps. The array was already sorted after pass 3, but the algorithm only knows that because pass 4 swapped nothing. Note how the small value 1 moves left by only one place in each pass, while a large value can travel all the way right in one pass.

Bubble sort pseudocode

Indexes start at 0, as in the code of this lesson. A is the array and n is its length.

BUBBLE-SORT(A, n)
1  for end = n - 1 downto 1
2      swapped = false
3      for j = 0 to end - 1
4          if A[j] > A[j + 1]
5              exchange A[j] with A[j + 1]
6              swapped = true
7      if not swapped
8          break

The outer loop shrinks the unsorted part by one element per pass, and lines 7 and 8 are the early exit described above.

Time and space complexity

A pass makes up to n - 1 comparisons, and up to n - 1 passes may be needed, which is about n²/2 comparisons.

Complexity

Best case time	O(n)
Average case time	O(n²)
Worst case time	O(n²)
Extra space	O(1)

• Best, O(n): the array is already sorted, so one pass finds no swap and stops.
• Average, O(n²): on shuffled input about half of the pairs are out of order, and nearly all the passes are still needed.
• Worst, O(n²): a reversed array, where every comparison is a swap.
• Space, O(1): it sorts in place, using only a few variables.

It is also stable: equal values are never swapped, so they keep their original order.

When to use it, and when not to

Almost never in real code. It is simple to write and easy to follow, which makes it a good first sorting algorithm to understand, but insertion sort does less work on nearly every input. For large data, use an O(n log n) algorithm.

Where bubble sort is used

Production code rarely uses bubble sort, so this list is short on purpose.

• Teaching and analysis. Knuth analyzes it in section 5.2.2 of volume 3 and finds little to recommend it over other simple sorts. It stays a standard first example of swaps, passes and an invariant.
• Checking whether data is sorted. With the early exit, one pass over sorted data makes n - 1 comparisons and no swap, so the pass also answers "is this array already in order?".
• Parallel hardware. A close relative, odd-even transposition sort, compares neighbor pairs that do not overlap at the same time. With n processors in a row it sorts n values in n rounds, which a one-pair-at-a-time scan like bubble sort cannot match.

Common mistake and edge cases

Related algorithms and variations

Large values travel right quickly, but small values creep left by one place per pass, as the value 1 did above. Cocktail shaker sort alternates left-to-right and right-to-left passes to move both kinds faster, and comb sort compares elements far apart first and shrinks the gap toward 1.

For the same simple idea with less work, see insertion sort (bubble sort vs insertion sort), or selection sort, which swaps far less often (bubble sort vs selection sort). For large inputs, move to merge sort or quick sort.