Sorting a list of items into order is one of the most common tasks in computing. There are many different algorithms for doing this, each with different trade-offs. Bubble sort is one of the simplest to understand, making it a perfect starting point. It works by repeatedly comparing neighbouring items and swapping them if they are in the wrong order.
How Bubble Sort Works
Imagine you have the list [5, 3, 8, 1, 4] and want to sort it in ascending order.
In each pass, you go through the list from left to right, comparing each pair of adjacent items:
- If the left item is greater than the right item, swap them.
- Otherwise, move on.
After one full pass, the largest item has "bubbled up" to the end. After each subsequent pass, the next largest item reaches its correct position.
Pass 1 through [5, 3, 8, 1, 4]:
| Step | Comparison | Action | List |
|---|---|---|---|
| 1 | 5 vs 3 | Swap | [3, 5, 8, 1, 4] |
| 2 | 5 vs 8 | No swap | [3, 5, 8, 1, 4] |
| 3 | 8 vs 1 | Swap | [3, 5, 1, 8, 4] |
| 4 | 8 vs 4 | Swap | [3, 5, 1, 4, 8] |
After pass 1, 8 is at the end — its correct position.
Python Implementation
def bubble_sort(items):
n = len(items)
for pass_num in range(n - 1):
for i in range(n - 1 - pass_num):
if items[i] > items[i + 1]:
# Swap adjacent items
items[i], items[i + 1] = items[i + 1], items[i]
return items
numbers = [5, 3, 8, 1, 4]
print(bubble_sort(numbers)) # [1, 3, 4, 5, 8]
The Python swap a, b = b, a is a clean, idiomatic way to swap two variables in one line without needing a temporary variable. In most other languages you would write: temp = a; a = b; b = temp.
Number of Comparisons
For a list of n items, bubble sort makes roughly n²/2 comparisons in the worst case. This means:
- 10 items → ~50 comparisons
- 100 items → ~5,000 comparisons
- 1,000 items → ~500,000 comparisons
The work grows very quickly — this is why bubble sort is not used for large datasets in practice.
You can add an optimisation: track whether any swaps happened during a pass. If no swaps occurred, the list is already sorted and you can stop early.
Optimised Version
def bubble_sort_optimised(items):
n = len(items)
for pass_num in range(n - 1):
swapped = False
for i in range(n - 1 - pass_num):
if items[i] > items[i + 1]:
items[i], items[i + 1] = items[i + 1], items[i]
swapped = True
if not swapped:
break # list is sorted, no need to continue
return items
Bubble sort has O(n²) time complexity, meaning it becomes very slow for large lists. In real applications, Python's built-in sorted() function uses a much faster algorithm. Bubble sort is mainly studied to understand the concept of sorting algorithms.
Practice Problems
After one complete pass of bubble sort on [9, 4, 6, 2, 7], what will the list look like?
Show answer
How many passes does bubble sort need in the worst case for a list of 5 items? Explain why.