programmingconcepts

§ 3.3 · Algorithms

Bubble sort

Walk the list swapping neighbours that are out of order; each pass carries the largest remaining value to the end.

Bubble sort repeatedly walks through a list and swaps each pair of neighbours that are in the wrong order, so the largest unsorted value bubbles to the end on every pass. It takes O(n²) comparisons on average and in the worst case, O(n) on already-sorted input with an early exit, and sorts in place. It is mainly a teaching example.

Average
O(n²)
Best
O(n) when already sorted
Extra space
O(1)
Stable
Yes
Requires
ArraysBig O
def bubble_sort(a):
    for end in range(len(a) - 1, 0, -1):
        swapped = False
        for j in range(end):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break

Press Play or Step to start.

0 comparisons0 swapsstep 0 / 00 / 12 in placecomparingmovingpivot

Fig. 3.3. Blue bars are the two neighbours being compared, orange bars are swapping, and black bars have reached their final place at the end.

Intuition

Line people up by height and walk along the line, swapping any neighbours where the taller one stands first. By the end of the walk, the tallest person has been passed along to the far end. Walk again and the second tallest ends up next to them. Repeat until a walk makes no swaps.

How it works

  1. Compare a[0] with a[1]; swap them if the first is larger.
  2. Move one step right and repeat, up to the end of the unsorted part.
  3. The largest value is now last. Shrink the unsorted part by one.
  4. Start the next pass. If a whole pass made no swaps, the list is sorted: stop early.

Complexity

Case Comparisons Swaps When it happens
Best n − 1 0 Already sorted: one pass, then the early exit.
Worst n(n − 1)/2 n(n − 1)/2 Reversed: every comparison swaps.

Each swap fixes exactly one pair that was out of order, so the number of swaps always equals the number of such pairs in the input.

Common mistakes

  1. No early exit. Without the swapped check, bubble sort does n(n − 1)/2 comparisons even on sorted input.
  2. Running past the end. The inner loop compares a[j] with a[j + 1], so it must stop one short of the unsorted part’s end.
  3. Re-checking the sorted tail. Each pass can stop one position earlier than the last, because the end is already final.

When to use it

For teaching, and for tiny lists that are almost sorted. Insertion sort does the same job with fewer operations, and anything larger should use your language’s built-in sort.

Check yourself

Check yourself

After the first pass over [5, 1, 4, 2, 8], which value is certain to be in its final place?

Check yourself

How many swaps does bubble sort make on [1, 2, 3, 4, 5]?

Sources

  • Donald Knuth, The Art of Computer Programming, Vol. 3, section 5.2.2.
  • Owen Astrachan, “Bubble Sort: An Archaeological Algorithmic Analysis,” SIGCSE 2003.

Newsletter

One new concept each week, by email.

Signup opens soon.