Bubble Sort — Algorithms & DS

Bubble sort is the algorithm nobody ships but everyone should understand. Its O(n²) behavior makes it impractical at scale, but it makes the cost of sorting concrete: every swap, every comparison, visible and countable. Once you understand why bubble sort is slow, you understand what merge sort and quicksort are actually buying you.

How it works

Bubble sort makes repeated passes through the array. On each pass, it compares adjacent elements and swaps them if they're in the wrong order. After the first pass, the largest element has "bubbled" to the last position. After the second pass, the second-largest is in place. And so on.

c

void bubble_sort(int *arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp  = arr[j];
                arr[j]   = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}
          

The inner loop bound shrinks by one each pass (n - 1 - i) because the last i elements are already sorted. This halves the total work compared to always going to n — but the complexity is still O(n²).

Why O(n²)

The outer loop runs n−1 times. The inner loop runs n−1, n−2, …, 1 times. Total comparisons: (n−1) + (n−2) + … + 1 = n(n−1)/2 ≈ n²/2. Dropping the constant: O(n²).

On 1,000 elements that's ~500,000 comparisons. On 10,000 elements it's ~50,000,000. Double the input, quadruple the work. That's the O(n²) signature.

The optimized version

One improvement: if a complete pass makes zero swaps, the array is already sorted and we can stop early. This turns best-case complexity (already-sorted input) from O(n²) to O(n). The worst case is still O(n²).

c

void bubble_sort_opt(int *arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp  = arr[j];
                arr[j]   = arr[j + 1];
                arr[j + 1] = tmp;
                swapped  = 1;
            }
        }
        if (!swapped) break;  // already sorted
    }
}
          

💡

Why not just use this optimization always? In practice, "nearly sorted" input is better served by insertion sort, which does less work even in the non-terminating case. The early-exit optimization makes bubble sort less terrible on sorted input, but insertion sort beats it on everything else too.

one-line takeaway

Bubble sort is O(n²) comparisons and O(n²) swaps — understanding its cost is exactly why O(n log n) sorts matter.

The visualization

Step through the sort below. Blue bars are being compared, amber bars are being swapped, green bars are in their final sorted position.