How Bubble Sort Works
Bubble sort compares each pair of neighbours and swaps them when they are the wrong way round, repeating until a pass makes no swaps. Watch it run step by step, then read the implementation in Python, JavaScript and Java.
- Waiting
- Being compared
- Just moved
- In final position
Step 1 of 102
Bubble sort, 12 values in random order.
Counters
- Comparisons
- 0
- Writes
- 0
- n
- 12
- Average case
- O(n²)
Settings
Two to 48 numbers. Sorted in exactly the order you type them.
Bubble sort
- 1
for i in 0..n-1: - 2
swapped = false - 3
for j in 0..n-i-2: - 4
if a[j] > a[j+1]: - 5
swap(j, j+1) - 6
swapped = true - 7
// a[n-1-i] is now final - 8
if not swapped: break
The same array, every algorithm
Comparisons on the values above, cheapest first. Writes in the second line. Run it on nearly sorted values to see the O(n log n) sorts lose.
- Merge3344 writes
- Quick3340 writes
- Insertion4042 writes
- Shell4637 writes
- Heap5166 writes
- Bubble6062 writes
- Selection6618 writes
How the seven compare
| Algorithm | Best | Average | Worst | Extra memory | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Shell | O(n log n) | O(n√n) | O(n²) | O(1) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Stable means equal values keep their original order.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(n) | O(n²) | O(n²) | O(1) |
The O(n) best case needs the early exit: without the swapped flag, an already sorted array still costs n² comparisons.
How bubble sort works
Bubble sort walks the array comparing each element with the one after it, swapping the pair when they are out of order. Each full pass drags the largest remaining value to the end — that is the bubble — so after k passes the last k positions are final. When a pass completes with no swaps at all, the array is sorted and the algorithm stops.
- Walk from the start of the unsorted region to its end, comparing each element with its neighbour.
- Swap the pair whenever the left one is larger. The largest value in the region moves one step right on every comparison it wins.
- At the end of the pass, the last position of the region holds the largest value and is never touched again; shrink the region by one.
- Track whether any swap happened. If none did, every neighbour is already in order, which means the whole array is — stop early.
- Repeat until the region has one element left.
Implementation
The same algorithm the visualiser is running, written to be read.
def bubble_sort(values):
n = len(values)
for end in range(n - 1, 0, -1):
swapped = False
for i in range(end):
if values[i] > values[i + 1]:
values[i], values[i + 1] = values[i + 1], values[i]
swapped = True
# No swaps in a full pass means every neighbour is in order.
if not swapped:
break
return valuesWhen to use it
- Use it to teach or to reason about: the invariant is a single sentence, and the swap count is exactly the number of inversions in the input, which is a genuinely useful measure.
- Use it on data that is nearly sorted and tiny, where the early exit turns it into one cheap verifying pass.
- Avoid it everywhere else. On random data it does about n²/2 comparisons and n²/4 swaps, and insertion sort does the same job with a quarter of the writes.
Check yourself
If the animation made sense, these should too.
Where does the early exit come from, and what does it buy?
From the swapped flag. If a full pass makes no swaps, every neighbouring pair is in order, which means the whole array is - so the algorithm can stop. Without it, an already sorted array still costs the full n² comparisons; with it, the best case is a single O(n) verifying pass.
Bubble sort and insertion sort are both O(n²). Why is insertion sort faster in practice?
They do a similar number of comparisons, but bubble sort moves data with swaps - three assignments each - while insertion sort shifts one value at a time and writes the held key once. On random input that is roughly four times the writes for the same work.