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. Matters when sorting by one key but you want to keep the order from a previous sort.

When to use it

Almost never in production. Its only real advantages:

• Easy to explain. It’s the textbook example for teaching sorting.
• Easy to implement correctly. The loop bounds and swap logic are simple.
• Detects sortedness. With the early-exit optimization it’s $O(n)$ on already-sorted input, handy if the list might already be mostly sorted.

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”

Large elements “bubble up” to the top (end) of the array each pass, like air bubbles rising in water.

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