Bubble Sort - Introduction to Programming - Python

Bubble Sort

Sorting by repeatedly swapping adjacent out-of-order elements, with an early exit optimization for nearly sorted data.

Bubble Sort

Bubble Sort works by repeatedly walking through the list and swapping any adjacent pair that is out of order. After each full pass, the largest unsorted element "bubbles up" to its correct position at the end. The algorithm performs $n-1$ such passes.

Python allows swapping two variables in a single line without a temporary variable: a[i], a[i + 1] = a[i + 1], a[i].

Example

Early Exit Optimization

If no swap was made during a full pass, the array is already sorted and we can stop early:

With this optimization, Bubble Sort runs in $O(N)$ on an already sorted array.

Summary

Case	Complexity
Worst / Average	$O(N^2)$

Up next

Selection sort

Sorting by repeatedly finding the minimum of the unsorted suffix and placing it in its correct position.

def bubble_sort(a):
    n = len(a)
    for it in range(n - 1):
        swapped = False
        for i in range(n - 1):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break