Bubble Sort
Swap neighbours.
Bubble sort is the simplest sorting algorithm to understand. Walk along the list, and whenever two neighbours are in the wrong order, swap them. After each pass, the biggest remaining item has bubbled up to the end.

- Walk along the list
- Swap neighbours in the wrong order
- The biggest bubbles to the end
Watching the bubbles
The outer loop counts the passes. The inner loop compares each pair of neighbours, and swaps them if they're the wrong way round. Each pass can stop one place earlier, because the end is already sorted. We print the list after each pass. Run it. Watch nine bubble to the end first, then seven, then five.
def bubble_sort(nums):
n = len(nums)
for i in range(n - 1):
for j in range(n - 1 - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
print(f"pass {i + 1}: {nums}")
return nums
bubble_sort([5, 2, 9, 1, 7])pass 1: [2, 5, 1, 7, 9] pass 2: [2, 1, 5, 7, 9] pass 3: [1, 2, 5, 7, 9] pass 4: [1, 2, 5, 7, 9]
Bubble sort cost
There's a loop inside a loop, so bubble sort is O of N squared. That's fine for ten items, and hopeless for a million. It's mainly used for teaching. A small improvement is to stop early if a whole pass makes no swaps, because then the list is already sorted.
| key | value |
|---|---|
| Time | O(n²) |
| Space | O(1), in place |
| Best case | O(n) with early stop |
| Use | teaching, tiny lists |
Summary
Bubble sort swaps neighbours until the list is sorted. It's simple, but O of N squared. Next, selection sort.
Key takeaways- Compare neighbours
- Swap if wrong
- O(n²)