Bubble Sort

Bubble sort repeatedly steps through the list, swapping adjacent out-of-order pairs until a pass makes no swaps. It is the canonical "first sort you learn" — easy to understand, almost never the right choice in production.

Complexity

How it works

On each pass, compare every adjacent pair (i, i+1) and swap if out of order. The largest element "bubbles" to the end on the first pass, the second-largest on the second pass, etc. With an early-exit flag, a pass that swaps nothing means the array is sorted — that gives the O(n) best case on already-sorted input.

Python implementation

def bubble_sort(arr):
    """In-place bubble sort with early-exit optimization."""
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr


print(bubble_sort([3, 6, 1, 8, 2, 9, 4]))  # [1, 2, 3, 4, 6, 8, 9]

Trade-offs

• Stable, in-place, O(1) extra memory.
• O(n²) average and worst — unusable on large inputs.
• Useful only as a teaching tool or for tiny (n < 10) arrays.
• Insertion sort beats it on every dimension; pick that instead.

← Back to Algorithms

1. Summary

Bubble sort is the simplest exchange sort. It makes repeated passes over the array, comparing each pair of neighbours and swapping them if they are out of order. After the first pass the largest element is guaranteed to be in the last position; after the second, the two largest are in place; and so on, so each pass can stop one element earlier than the one before. With an early-exit flag that records whether any swap happened, an already sorted array is detected in a single pass, giving the best case of O(n). The algorithm is stable, because equal neighbours are never swapped, and in-place.

2. Pass-by-pass trace

Each row shows the array after one complete pass. The green suffix is the region that is already final. Notice that small values move left slowly, only one position per pass, while large values can travel all the way right in a single pass. Elements that move slowly are called turtles, and they are the reason bubble sort needs many passes on inputs where a small value starts near the end. Cocktail shaker sort alternates direction to move turtles faster, and comb sort compares elements a shrinking gap apart for the same reason.

3. Inside a single pass

Within a pass the algorithm only ever looks at two adjacent cells. A swap happens when the left value is larger. Because the currently largest value seen keeps winning comparisons, it is carried to the right like a bubble rising to the surface, which gives the algorithm its name. Every swap removes exactly one inversion (a pair that is out of order), so the number of swaps equals the number of inversions in the input.

4. Worked example: counting work

def bubble_sort_stats(arr):
    a = list(arr)
    n, comps, swaps, passes = len(a), 0, 0, 0
    for i in range(n - 1):
        passes += 1
        swapped = False
        for j in range(n - 1 - i):
            comps += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swaps += 1
                swapped = True
        if not swapped:
            break
    return a, comps, swaps, passes

for data in ([1, 2, 3, 4, 5], [3, 6, 1, 8, 2, 9, 4], [5, 4, 3, 2, 1]):
    print(data, "->", bubble_sort_stats(data)[1:])
# [1, 2, 3, 4, 5]       -> (4, 0, 1)    best case: one pass
# [3, 6, 1, 8, 2, 9, 4] -> (18, 8, 4)
# [5, 4, 3, 2, 1]       -> (10, 10, 4)  worst case: every pair inverted

The counts confirm the theory: sorted input needs n - 1 comparisons and no swaps; reversed input needs n(n - 1)/2 of each; and the swap count for the sample array (8) equals its inversion count.

5. Trade-offs and when to use

Bubble sort is useful for teaching, for checking whether an array is already sorted in one pass, and on tiny arrays where code size matters more than speed. For anything else, insertion sort does the same job with fewer writes, and Python's built-in sorted() is far faster.

There is one more practical use: because a single bubble pass is cheap and local, it can maintain a nearly sorted list that changes slightly between frames, such as a z-order list in a simple graphics loop. A pass or two per frame moves slightly out-of-order items back into place without a full sort. Even there, insertion sort is usually the cleaner tool, but the idea of a bounded number of local passes is worth recognising. In interviews, bubble sort is mainly a vehicle for discussing stability, adaptivity, inversion counts and why quadratic algorithms stop scaling around a few thousand elements.

6. Pitfalls

• Omitting the early-exit flag, which makes the best case O(n^2).
• Not shrinking the inner loop by i, which wastes comparisons on the sorted suffix.
• Using >= instead of >, which breaks stability.

7. Related topics

• Insertion Sort
• Selection Sort
• Shell Sort
• Simple sorts overview

Featured Videos