Bubble Sort

Bubble sort works by repeatedly walking through the array and swapping adjacent elements that are out of order. Each full pass guarantees that the largest unsorted element "bubbles up" to its correct position at the right end.

The name is literal. Imagine the array is a column of liquid — heavier elements (larger values) sink to the bottom, lighter elements (smaller values) rise to the top. Each pass lets the heaviest remaining element settle one level further right. After n-1 passes, every element has reached its final position.

The key insight is that one swap can only move an element one position. To move the largest element from index 0 to index n-1, it must be swapped n-1 times across a single pass. After that pass, the largest element is permanently placed and never touched again.

Step-by-Step Trace

Starting array: [64, 34, 25, 12, 22]

Pass 1 — largest element (64) bubbles to its final position:

[64, 34, 25, 12, 22]
 ^   ^                   64 > 34 → swap
[34, 64, 25, 12, 22]
     ^   ^               64 > 25 → swap
[34, 25, 64, 12, 22]
         ^   ^           64 > 12 → swap
[34, 25, 12, 64, 22]
             ^   ^       64 > 22 → swap
[34, 25, 12, 22, 64] ✓   pass complete, 64 settled

Pass 2 — largest remaining (34) bubbles right:

[34, 25, 12, 22, 64]
 ^   ^                   34 > 25 → swap
[25, 34, 12, 22, 64]
     ^   ^               34 > 12 → swap
[25, 12, 34, 22, 64]
         ^   ^           34 > 22 → swap
[25, 12, 22, 34, 64] ✓✓  pass complete, 34 settled

Pass 3 — largest remaining (25) bubbles right:

[25, 12, 22, 34, 64]
 ^   ^                   25 > 12 → swap
[12, 25, 22, 34, 64]
     ^   ^               25 > 22 → swap
[12, 22, 25, 34, 64] ✓✓✓ pass complete, 25 settled

Pass 4 — largest remaining (22) bubbles right:

[12, 22, 25, 34, 64]
 ^   ^                   12 < 22 → no swap
[12, 22, 25, 34, 64] ✓✓✓✓ pass complete, 22 settled

Result: [12, 22, 25, 34, 64] — sorted in 4 passes.

Naive Implementation

fn bubble_sort(arr: &mut Vec<i32>) {
    let n = arr.len();
 
    // Outer loop: we need at most n-1 passes.
    // After pass i, the last i+1 elements are sorted.
    for i in 0..n {
        // Inner loop: compare each adjacent pair.
        // The last i elements are already settled, so stop early.
        for j in 0..n - 1 - i {
            // If the left neighbour is larger, they are out of order.
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1); // swap in place — no extra allocation
            }
        }
    }
}

This is correct but has one flaw: even if the array becomes fully sorted after pass 2, the outer loop keeps running until pass n-1, doing useless work. The optimized version fixes this.

Optimized Implementation

Two improvements over the naive version:

1. Early exit via swapped flag — if a full pass makes zero swaps, the array is already sorted and we stop. This gives O(n) best-case on nearly-sorted input.
2. Cocktail shaker sort — instead of only sweeping left-to-right, alternate between a forward sweep (bubbles the max to the right) and a backward sweep (bubbles the min to the left). This cuts the number of passes roughly in half on average and handles "turtles" (small elements near the right end) that bubble left very slowly in standard bubble sort.

fn bubble_sort_optimized(arr: &mut Vec<i32>) {
    let mut left = 0;           // left boundary of unsorted region
    let mut right = arr.len();  // right boundary of unsorted region (exclusive)
 
    loop {
        let mut swapped = false;
 
        // Forward sweep: move the largest unsorted element to `right - 1`.
        for i in left..right - 1 {
            if arr[i] > arr[i + 1] {
                arr.swap(i, i + 1);
                swapped = true;
            }
        }
        right -= 1; // rightmost element is now settled
 
        // Early exit: if no swaps occurred, array is sorted.
        if !swapped {
            break;
        }
 
        swapped = false;
 
        // Backward sweep: move the smallest unsorted element to `left`.
        for i in (left..right - 1).rev() {
            if arr[i] > arr[i + 1] {
                arr.swap(i, i + 1);
                swapped = true;
            }
        }
        left += 1; // leftmost element is now settled
 
        // Early exit again after the backward sweep.
        if !swapped {
            break;
        }
    }
}

The left and right bounds shrink from both sides each iteration, so the unsorted region narrows twice as fast as in the naive version.

Time Complexity

Counting comparisons precisely.

In the naive version, pass i (0-indexed) compares elements at positions 0..n-2-i, giving n-1-i comparisons. Summing over all passes:

Total comparisons = (n-1) + (n-2) + (n-3) + ... + 1
                  = Σ k  for k = 1 to n-1
                  = n(n-1) / 2

For n = 5 this is 5×4/2 = 10, matching the trace above (4+3+2+1 = 10 comparisons).

Worst case — O(n²)

Occurs on a reverse-sorted array: every comparison triggers a swap. Both comparisons and swaps hit n(n-1)/2 ≈ n²/2, so T(n) = Θ(n²).

Best case (optimized) — O(n)

Occurs on an already-sorted array: the first forward sweep makes n-1 comparisons and zero swaps. The swapped flag is still false, so we break immediately. Total work = n-1 comparisons = O(n).

Average case — O(n²)

For a randomly ordered array, roughly half of adjacent pairs are out of order on each pass. The expected number of swaps per pass is ~(n-1)/2, but the comparison count is always exactly n-1-i per pass. The total comparisons are still n(n-1)/2 regardless, giving O(n²) average.

Space Complexity

Bubble sort is O(1) auxiliary space. The only variable added beyond the input array is the swapped flag and a few loop indices — a constant number of machine words regardless of n. All swaps happen in-place using arr.swap(i, j), which exchanges two elements without allocating a temporary array.