Bubble sort

Bubble sort sorts an array by repeatedly stepping through it, comparing adjacent pairs and swapping them if they’re in the wrong order. After each pass, the largest unsorted element “bubbles up” to its correct position at the end.

void bubbleSort(int arr[], int n) {
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

After the first pass, the largest element is at the end. After the second pass, the second-largest is in its place. After $n-1$ passes, the array is sorted.

Big O

• Best case: $O(n)$ if you optimize to detect when no swaps happened during a pass (the array is already sorted, you can exit early). Without this optimization, $O(n^2)$.
• Average case: $O(n^2)$. The expected number of swaps is $n(n-1)/4$ — but this average assumes each input permutation is equally likely (the “uniformly random permutation” model). On real-world inputs that are partially sorted, the swap count is much smaller.
• Worst case: $O(n^2)$ — when input is reverse-sorted, every adjacent pair needs a swap.

The number of comparisons is always $O(n^2)$ — you have $n-1$ passes, each doing roughly $n$ comparisons.

Stability

Bubble sort is stable — it never swaps equal adjacent elements (the comparison is strictly >), so the relative order of equal elements is preserved. This matters when sorting by one key while wanting to preserve order from a previous sort.

When to use it

Almost never in production. Bubble sort’s only practical advantages are:

1. Easy to explain. It’s the textbook example for teaching sorting.
2. Easy to implement correctly. The loop bounds and swap logic are simple.
3. Detects sortedness. With the early-exit optimization, it’s $O(n)$ on already-sorted input — useful if “is this list mostly sorted?” might be true.

For nearly-sorted data, insertion sort is similar in spirit but typically faster because it shifts elements rather than swapping each adjacent pair. For arbitrary data, $O(n\log n)$ algorithms (Heap sort, Merge sort, Quick sort) win on any reasonably-sized input.

Why “bubble”

The metaphor: large elements “bubble up” to the top (end) of the array, like air bubbles rising in water. After one pass, the largest is at the top. After two passes, the two largest are. And so on.

For other quadratic-time sorts, see Selection sort. For better general-purpose sorts, see Quick sort and Merge sort.