Bubble Sort

Repeatedly swap neighbouring items until the list is in order.

A bubble sort puts a list in order by repeatedly comparing each pair of neighbouring items and swapping them if they are the wrong way round. With each pass the largest remaining value 'bubbles' up to its place at the end. It is the simplest sorting algorithm to understand.

Swapping two values

Sorting is mostly about swapping items into order. To swap two variables you need a third, temporary variable to hold one value while you move the other.

swap.py

a = 9
b = 6
temp = a
a = b
b = temp
print(a, b)

Output

6 9

Follow each statement in a trace table to see how the values move:

Statement	temp	a	b
(start)	—	9	6
`temp = a`	9	9	6
`a = b`	9	6	6
`b = temp`	9	6	9

Why you need tempIf you just wrote a = b then b = a, the first line overwrites a with 6, so the original 9 is lost — and b = a only copies 6 back. Both end up 6. The temporary variable keeps the value safe.

Python's shortcutPython can swap in one line: a, b = b, a. It does the same job without a temp variable. The temp version is shown because it makes clear what a swap really involves.

One pass of a bubble sort

In a single pass the algorithm compares each neighbouring pair from left to right, swapping any that are out of order. Watch the largest value, 15, move steadily to the end.

the pair being comparedin its final place

start

9541538112

9 > 5 → swap

5941538112

9 > 4 → swap

5491538112

9 < 15 → keep

5491538112

15 > 3 → swap

5493158112

15 > 8 → swap

5493815112

15 > 11 → swap

5493811152

15 > 2 → swap

5493811215

After one full pass the largest item (15) is guaranteed to be at the end. The next pass can ignore it, so each pass checks one fewer item.

Bubble sort in Python

bubble.py

numbers = [9, 5, 4, 15, 3, 8, 11, 2]
pass_number = len(numbers) - 1
swap_made = True

while pass_number > 0 and swap_made == True:
    swap_made = False
    for j in range(pass_number):
        if numbers[j] > numbers[j + 1]:
            temp = numbers[j]
            numbers[j] = numbers[j + 1]
            numbers[j + 1] = temp
            swap_made = True
    pass_number = pass_number - 1
    print(numbers)

Output

[5, 4, 9, 3, 8, 11, 2, 15]
[4, 5, 3, 8, 9, 2, 11, 15]
[4, 3, 5, 8, 2, 9, 11, 15]
[3, 4, 5, 2, 8, 9, 11, 15]
[3, 4, 2, 5, 8, 9, 11, 15]
[3, 2, 4, 5, 8, 9, 11, 15]
[2, 3, 4, 5, 8, 9, 11, 15]

How it works

The for loop does one pass, comparing each neighbour numbers[j] with numbers[j + 1].
If a pair is out of order, the three temp-swap lines put them right.
pass_number shrinks by 1 each time, because the largest value is already parked at the end.
Printing after each pass shows the list getting closer to sorted, with the sorted tail growing.

Stopping early with a flag

swap_made starts each pass as False. The moment a swap happens it becomes True. If a whole pass makes no swaps at all, the list must already be sorted, so the while loop stops instead of wasting time on more passes.

When to use itBubble sort is easy to write and follow, which makes it good for learning and for very small lists. It is slow on large lists, because it may make many comparisons and swaps.

What you have learned

A bubble sort repeatedly compares neighbouring pairs and swaps any in the wrong order.
After each pass the next largest value reaches its final place at the end.
Swapping two values needs a temporary variable so neither value is lost.
A swap_made flag lets the sort stop early once no swaps are needed.
Simple to understand, but slow on large lists.