Bubble SortBubble sort

01Why it exists

Reach for it when you see:Adjacent swaps, one largest value settled per pass, nearly sorted data you want to bail out of early, counting inversions, teaching or tiny inputs.

02The core idea

Bubble sort has exactly one rule: walk left to right over every pair of neighbours and swap whenever the left one is bigger. One pass carries the current maximum all the way to the right-hand end, like a bubble rising to the surface. That position is settled for good, so the next pass only scans the first n−1 cells, the one after that n−2, and after at most n−1 passes everything is in order.

Why is it correct? At the end of every pass, the largest value in the unsettled region has necessarily been pushed to that region's end: once the scan reaches it, it never loses a comparison against the element on its right, so it keeps swapping rightward (and on a tie, the element to its right takes over and carries on right). So after pass i, the last i elements are the i largest overall, already in order. Induct up to n−1 passes and you are done.

Complexity: pass i (counting from 1) makes n−i comparisons, and (n−1)+(n−2)+…+1 = n(n−1)/2 in total, so O(n²). The number of swaps equals the number of inversions (each swap removes exactly one adjacent inversion), which is n(n−1)/2 at worst (fully reversed) and 0 at best (already sorted). With the swapped flag, sorted input finishes after one pass, making the best case O(n); the average and worst cases stay O(n²). How many passes you need does not depend on how many elements are out of place but on how far the element that must travel furthest left has to go: in each pass, every element with a larger value still to its left moves exactly one slot left. Extra space is O(1).

Compared with its neighbours: selection sort makes a fixed number of comparisons but at most n−1 swaps; insertion sort costs O(n + inversions), so it approaches O(n) whenever there are few inversions, it is not thrown by a small value stuck at the end, and each step is a single shift rather than a full swap, giving it a smaller constant. That is why small arrays in practice get insertion sort rather than bubble sort. Bubble sort's value is pedagogical: it makes adjacent swaps, stability and inversions clear all at once.

03The algorithm

1. 1Outer loop i runs from 0 to n−2, one iteration per pass. Set swapped to False at the start of each pass.
2. 2Inner loop j runs from 0 to n−2−i: compare a[j] with a[j+1], and if the left one is bigger, swap them and set swapped to True.
3. 3At the end of the pass, a[n−1−i] holds that pass's largest value and is settled. Later passes never look at it again.
4. 4If swapped is still False, the pass found no inversions at all, the array is already sorted, and you can stop early.
5. 5For stability, only swap on a strict greater-than. Using >= makes equal elements trade places and the stability is gone.

04Interactive demo

The shared array [5, 2, 9, 1, 7, 3, 8, 4]. Each step is one comparison of neighbours, and both cells turn blue on a swap. Watch one more cell settle at the end of every pass (in green), and the fifth pass stop immediately because it made no swaps at all.

05Code

The basic version with the early exit, plus the bidirectional cocktail sort variant. Cocktail sort fixes the case where a small value at the very end needs n−1 passes to get back to the front (the so-called turtle), but that is the only case it helps with: the worst case is still O(n²).

# Bubble sort: compare neighbouring cells and swap the bigger one to the right.
# After each pass, that pass's largest element has been pushed to the end.
def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):          # the last i cells are settled, skip them
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:                      # a whole pass with no swap means it is sorted
            break
    return a


# Variant: cocktail sort (bidirectional bubble).
# One pass pushes the largest right, the next pushes the smallest left. Far quicker when a
# small value is stuck at the end (a "turtle"), but still O(n²) at worst: on a fully reversed
# input it makes exactly as many comparisons as bubble sort.
def cocktail_sort(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        swapped = False
        for j in range(lo, hi):             # push the largest right
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        hi -= 1
        for j in range(hi, lo, -1):         # push the smallest left
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                swapped = True
        lo += 1
        if not swapped:
            break
    return a


if __name__ == "__main__":
    print(bubble_sort([5, 2, 9, 1, 7, 3, 8, 4]))     # [1, 2, 3, 4, 5, 7, 8, 9]
    print(cocktail_sort([5, 2, 9, 1, 7, 3, 8, 4]))   # [1, 2, 3, 4, 5, 7, 8, 9]

06Practice

• LeetCode 1051Height Checker (sort, then count the positions that differ)Easy
• LeetCode 2717Semi-Ordered Permutation (minimum adjacent swaps: bubble 1 and n to the two ends)Easy
• LeetCode 283Move Zeroes (treat 0 as the largest value and do stable adjacent swaps, then work out the O(n) two-pointer version)Easy
• LeetCode 75Sort Colors (three values — can you beat O(n²)?)Medium
• LeetCode 3011Find if Array Can Be Sorted (you may only swap neighbours with the same popcount, so simulate bubble sort directly)Medium
• LeetCode 912Sort an Array (O(n²) times out — feel the difference)Medium