Skip to content
Tutorials Center
My learning

Topics

Lesson 78 of 225 · Sorting

Bubble Sort

Learn bubble sort in Python with a step-by-step trace, the swapped-flag optimisation, comparison and swap counters, O(n²) complexity and when (not) to use it.

Bubble sort is the simplest sorting algorithm to explain: walk through the list, and whenever two neighbours are in the wrong order, swap them. Repeat until a full walk makes no swaps. The big values "bubble up" to the end of the list, like bubbles rising in a glass of water, which gives the algorithm its name.

Nobody uses bubble sort for real work, because it is slow on large inputs. So why learn it? Because it is the cleanest way to see what sorting is: repeated local fixes that add up to a global order. It also teaches the ideas you need for every later sort: passes, invariants, swaps, early exit and counting operations. If you can explain bubble sort and why it is O(n²), you are ready for selection sort, insertion sort and the faster algorithms beyond them. If the words stable and in-place are new to you, read sorting basics first.

The idea

Compare each pair of neighbours from left to right. If the left one is bigger, swap. After one full pass, the largest value has travelled all the way to the right end, where it belongs. The next pass does the same for the rest, so the second-largest lands next to it, and so on.

TEXT
pass 1 on [5, 1, 4, 2, 8]

  5 1 4 2 8     compare 5,1 -> swap
  1 5 4 2 8     compare 5,4 -> swap
  1 4 5 2 8     compare 5,2 -> swap
  1 4 2 5 8     compare 5,8 -> fine
  -------------
  1 4 2 5 [8]   8 is now in its final place

The invariant: after pass k, the last k items are the k largest values, in their final positions. That means each new pass can stop one position earlier than the previous one.

The algorithm in plain words

  1. Set end to the last index.
  2. For i from 0 up to end - 1: if items[i] > items[i + 1], swap them.
  3. Now items[end] is final, so decrease end by one.
  4. Repeat from step 2 until end reaches 0.

A first implementation

Python Plain bubble sort with counters

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the counts for ten items. In the plain version the number of comparisons is always the same, whatever the input: 9 + 8 + ... + 1 = 45. Only the number of swaps changes: 45 for the reversed list (every pair is out of order) and 0 for the sorted list. Even when the list is already sorted, this version still makes all 45 comparisons. That is wasteful.

Optimisation: stop when nothing moved

If a whole pass makes no swaps, every neighbour pair is in order, so the list is sorted and we can stop. Add a swapped flag:

Python Bubble sort with the swapped flag, traced

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For [5, 1, 4, 2, 8] the list is fully sorted after pass 2, but the algorithm only knows that after pass 3 makes no swaps. It used 9 comparisons and 4 swaps in total. On an already sorted list it needs just one pass: n - 1 comparisons and no swaps, so the best case becomes O(n).

A second trick is also visible in the code: end -= 1 after each pass. Because the largest values have already settled at the right, there is no need to look at them again. You can even remember the position of the last swap in each pass and use it as the next end, since everything after it is already in order.

Counting the cost: O(n²)

The comparisons in the optimised algorithm are at most (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2, which is about n² / 2. We drop the constant and write O(n²). Doubling the input quadruples the work.

Case Comparisons Swaps Time
Best (sorted, with flag) n - 1 0 O(n)
Average (random) about n² / 2 about n² / 4 O(n²)
Worst (reversed) n(n - 1) / 2 n(n - 1) / 2 O(n²)

The average swap count is half of the worst case because, in a random list, about half of all pairs are out of order. The number of swaps always equals the number of inversions: pairs where a bigger item sits before a smaller one. Each swap of neighbours fixes exactly one inversion. Space is O(1): only a couple of variables.

Python Comparing input shapes for bubble sort

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In every row the number of swaps equals the number of inversions. As n doubles, comparisons and swaps grow roughly fourfold. That is the quadratic growth in action.

Stability and sorting records

Bubble sort only swaps when the left item is strictly greater than the right one. Equal items are never swapped, so their relative order never changes: bubble sort is stable. If you wrote >= instead of >, you would lose stability and also waste swaps, so keep the strict comparison.

Python Bubble sort is stable (sorting records by key)

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Bubble sort variants

  • Cocktail shaker sort alternates directions: a pass left to right carries the biggest item to the right, a pass right to left carries the smallest item to the left. It helps when a small value sits near the end (a "turtle"), which plain bubble sort moves left only one position per pass.
  • Comb sort compares items that are far apart first and shrinks the gap, similar in spirit to Shell sort.

In plain bubble sort, large values move right quickly (a "rabbit" can travel the whole list in one pass), but small values move left only one step per pass (a "turtle"). That asymmetry is why a list like [2, 3, 4, 5, 1] takes many passes: the 1 moves one place per pass.

When to use bubble sort

  • Teaching and interviews. It is the standard first example, and interviewers like the swapped-flag follow-up.
  • Tiny or almost sorted lists where simplicity matters more than speed. Even then, insertion sort does the same job with fewer operations, and Python's sorted() beats both.
  • Never for thousands of items. At 100,000 items the quadratic cost means billions of comparisons, while merge sort or Python's own sorted() needs under two million.

Common mistakes

  • Looping i up to len(items) - 1 inclusive, so that items[i + 1] raises IndexError. The inner loop must stop one earlier.
  • Forgetting to shrink the range after each pass (correct but slower), or shrinking it without the invariant to justify it.
  • Resetting swapped = False outside the pass loop, so the early exit never fires.
  • Using >= and breaking stability.
  • Believing bubble sort is "fast on average because of the early exit". The flag only helps on nearly sorted input.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. After the first full pass of bubble sort, what is guaranteed?

    Each comparison carries the larger of the two neighbours to the right, so the maximum travels all the way to the end during the first pass.
  2. 2. What is the running time of bubble sort with the swapped flag on an already sorted list of n items?

    One pass makes n - 1 comparisons and no swaps, so the flag stays False and the algorithm stops. The best case is linear.
  3. 3. How many swaps does bubble sort perform on a list with 7 inversions?

    Swapping two neighbouring items fixes exactly one inversion, and never creates one, so the total number of swaps is exactly the number of inversions.
  4. 4. Why is bubble sort stable?

    Equal neighbours are left alone, so they can never pass each other. Using >= would swap them and break stability.
  5. 5. Roughly how does the work change when the input size doubles?

    The work is about n² / 2 comparisons. Doubling n multiplies n² by four.

Summary

  • Bubble sort repeatedly swaps adjacent out-of-order items; after pass k the last k items are final.
  • A swapped flag stops early, giving O(n) on sorted input; shrinking the range each pass saves work.
  • Comparisons are up to n(n - 1) / 2, so the worst and average time is O(n²); space is O(1).
  • The number of swaps equals the number of inversions.
  • It is stable and in-place, but too slow for large inputs. Use sorted() in real code.

Next: Selection Sort