Bubble Sort

Bubble Sort

Bubble sort is the most intuitive sorting algorithm and the first one most programmers encounter. It earns its name from its behavior: larger elements “bubble up” to the end of the array through repeated adjacent swaps. While impractical for production use, bubble sort builds foundational intuition about swap-based sorting, inversions, and algorithm optimization — all concepts interviewers probe.

The Algorithm

Bubble sort works by making multiple passes through the array. In each pass, it compares every pair of adjacent elements and swaps them if they are out of order. After the first pass, the largest element sits in its final position at the end. After the second pass, the second-largest element is in place. This continues until no more swaps are needed.

Core invariant: After pass i, the last i elements are in their correct, final sorted positions.

Basic Implementation

void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap adjacent elements
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

The outer loop runs n - 1 passes. The inner loop shrinks by one each pass because the last i elements are already sorted — no need to compare them again.

Note the n - 1 - i bound: This optimization cuts the inner loop short. Without it, bubble sort would still produce the correct result, but it would waste comparisons on elements already in their final positions.

Visual Walkthrough

Consider sorting [5, 3, 8, 1, 2]:

Pass 1 (entire unsorted region):

[5, 3, 8, 1, 2]  → compare 5, 3 → swap  → [3, 5, 8, 1, 2]
[3, 5, 8, 1, 2]  → compare 5, 8 → no swap
[3, 5, 8, 1, 2]  → compare 8, 1 → swap  → [3, 5, 1, 8, 2]
[3, 5, 1, 8, 2]  → compare 8, 2 → swap  → [3, 5, 1, 2, 8]

After pass 1: 8 is in its final position. ✓

Pass 2 (ignore last element):

[3, 5, 1, 2, 8]  → compare 3, 5 → no swap
[3, 5, 1, 2, 8]  → compare 5, 1 → swap  → [3, 1, 5, 2, 8]
[3, 1, 5, 2, 8]  → compare 5, 2 → swap  → [3, 1, 2, 5, 8]

After pass 2: 5 is in its final position. ✓

Pass 3 (ignore last two):

[3, 1, 2, 5, 8]  → compare 3, 1 → swap  → [1, 3, 2, 5, 8]
[1, 3, 2, 5, 8]  → compare 3, 2 → swap  → [1, 2, 3, 5, 8]

After pass 3: 3 is in its final position. ✓

Pass 4 (ignore last three):

[1, 2, 3, 5, 8]  → compare 1, 2 → no swap

After pass 4: 2 is in its final position. ✓

Result: [1, 2, 3, 5, 8] — sorted.

The Optimization: Early Termination

The basic implementation always runs n - 1 passes, even if the array becomes sorted after pass 2. This wastes time. The fix: track whether any swaps occurred during a pass. If a full pass completes with zero swaps, the array is already sorted, and you can stop immediately.

void bubbleSortOptimized(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;  // Array is sorted — stop early
        }
    }
}

This single boolean flag transforms bubble sort’s best case from O(n²) to O(n).

Complexity Analysis

Time Complexity

Best case — O(n): The input is already sorted. The optimized version makes one pass, performs zero swaps, and exits. That single pass makes n - 1 comparisons. Total: O(n).

Average case — O(n²): For a random permutation, bubble sort performs approximately n²/4 swaps on average. Each pass eliminates one inversion, and a random array has Θ(n²) inversions.

Worst case — O(n²): The input is reverse sorted. Every pair is an inversion. Pass 1 makes n - 1 comparisons and swaps, pass 2 makes n - 2, and so on:

$$(n-1) + (n-2) + \ldots + 1 = \frac{n(n-1)}{2} = O(n^2)$$

Space Complexity

O(1) — Bubble sort is in-place. It uses a constant number of variables (temp, swapped, loop counters) regardless of input size.

Stability

Stable — Bubble sort compares adjacent elements and swaps them only when arr[j] > arr[j + 1] (strict inequality). Equal elements are never swapped, so their relative order is preserved.

If you changed the condition to arr[j] >= arr[j + 1], bubble sort would become unstable. Pay attention to this detail — interviewers will probe it.

Summary

Metric	Value
Best time	O(n) — sorted input, early termination
Average time	O(n²)
Worst time	O(n²) — reverse sorted
Space	O(1)
Stable	Yes
Adaptive	Yes (with early termination)

Counting Inversions: The Connection

An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. Bubble sort performs exactly one swap per inversion it eliminates. The total number of swaps equals the number of inversions in the array.

• Sorted array: 0 inversions → 0 swaps → O(n) with early termination.
• Reverse sorted array: $\frac{n(n-1)}{2}$ inversions → maximum swaps → O(n²).
• Random array: expected $\frac{n(n-1)}{4}$ inversions → Θ(n²) swaps.

This connection makes bubble sort useful for counting inversions — though merge sort does it more efficiently in O(n log n).

Cocktail Shaker Sort: The Bidirectional Variant

Standard bubble sort scans left to right, moving large elements toward the end. Cocktail shaker sort (also called bidirectional bubble sort) alternates direction: left-to-right on odd passes, right-to-left on even passes. This addresses the “turtle problem” — small elements near the end that take many passes to reach the front.

Cocktail shaker sort has the same O(n²) worst-case complexity but performs better on certain pathological inputs. You won’t implement it in an interview — knowing it exists demonstrates awareness of sort variants.

When Bubble Sort Wins

Bubble sort has a narrow advantage in specific scenarios:

• Tiny arrays (< 10 elements): The overhead of more sophisticated algorithms (recursion, partitioning) outweighs bubble sort’s quadratic cost. For 5 elements, bubble sort needs at most 10 comparisons.
• Nearly sorted data with early termination: If the array has only a few elements out of place, the optimized version detects this and terminates in O(n).
• Teaching tool: No other algorithm illustrates adjacency swaps, inversions, and optimization so cleanly.

For everything else — use insertion sort for small/nearly-sorted data, and merge sort or quick sort for general-purpose sorting.

Interviewer Tips

Never propose bubble sort as your sorting solution in a coding interview. Interviewers expect you to reach for O(n log n) algorithms. Saying “I’ll use bubble sort” signals inexperience.

Do know bubble sort for analysis questions. An interviewer who asks “What’s the simplest sorting algorithm?” or “Explain an O(n²) sort” expects you to describe bubble sort fluently, including its optimization and complexity breakdown.

Use it as a stepping stone: When an interviewer asks you to sort, start with “The brute force approach would be O(n²) using something like bubble sort. Let me optimize to O(n log n) with…” This shows structured thinking — you acknowledge the naive solution and then improve.

Know the inversion connection: If asked “How many swaps does bubble sort perform?”, answer with the inversion count. This demonstrates understanding beyond surface-level mechanics.