Bubble Sort

Bubble sort walks the array from left to right, comparing each element to its right-hand neighbor and swapping the two if they're out of order. After one full pass the largest element has "bubbled" to the end. Repeat, and the array is sorted.

The orange bars are the pair currently being compared. When they're out of order they turn rose and slide past each other — one arcs over the top so you can see which slot it's coming from. As the algorithm finishes a pass, the largest unsorted element settles at the right and turns green; that column is fixed for the rest of the run.

Swapping two values

The atomic operation under every comparison sort is the swap. The classic form uses a temporary variable; Python lets you write it as a single parallel assignment.

# Swap with a temporary variable — works in any language.
tmp = a
a = b
b = tmp

# Or in Python, using tuple unpacking:
a, b = b, a

The algorithm

Two nested loops: the outer loop counts how many passes have completed, the inner loop walks once across the still-unsorted prefix. The swapped flag short-circuits the run as soon as a pass goes by without any swaps — a cheap win when the input is already nearly sorted.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:           # array already sorted
            break
    return arr


# Example
print(bubble_sort([3, 1, 2, 5, 4]))
# [1, 2, 3, 4, 5]

Complexity

Worst-case (reverse-sorted input) requires a full triangle of comparisons and swaps: O(n²) comparisons and O(n²) swaps. Best-case (already-sorted input) takes a single O(n) pass thanks to the swapped short-circuit. Average case is O(n²). Memory: O(1) — the swap is in-place.

Bubble sort is mostly a teaching algorithm; for practical sorting use merge sort, quick sort, or your language's built-in (which is usually Timsort or introsort). But the comparison-and-swap pattern shown above generalizes to selection sort and insertion sort, and the visualizer on this page works for any of them — just plug in a different action generator.

Trace it by hand