Bubble sort compares neighbouring elements and swaps them if they are in the wrong order. After a pass the largest element “bubbles up” to the end. It is the simplest sorting algorithm and a good first example of invariants and O(n²) analysis. For the properties used below see sorting properties.

Bubble sort on 5 1 4 2 8
Bubble sort on 5 1 4 2 8

The algorithm

For each pass i we compare the pairs a[j], a[j + 1] for j up to n - 1 - i, since the last i elements are already in place. Invariant: after i passes the last i elements are the i largest, in sorted order.

python
a = [5, 1, 4, 2, 8]
n = len(a)
for i in range(n - 1):
    swapped = False
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
            swapped = True
    print("pass", i + 1, a)
    if not swapped:
        break
text
pass 1 [1, 4, 2, 5, 8]
pass 2 [1, 2, 4, 5, 8]
pass 3 [1, 2, 4, 5, 8]

Implementation with an early exit

If a pass made no swaps, the array is already sorted and we can stop. For this we keep a swapped flag.