Bubble Sort

Explanation

Bubble sort works by making multiple passes through the array. In each pass, it compares adjacent pairs and swaps if out of order. After the first pass, the largest element is in the last position. After the second pass, the second largest is in the second-to-last position. After n-1 passes, the array is sorted. This is O(n²) time in the worst and average case, O(n) in the best case (already sorted array with an early-exit optimization). The name comes from the visual analogy: larger elements "bubble up" to the end of the array, like bubbles rising to the surface of water. It's intuitive to understand, which is why it's taught first in CS courses. In practice, it's almost never used in production code — JavaScript's Array.prototype.sort(), Python's sorted(), and virtually every other standard library sorting function uses a hybrid algorithm (Timsort, introsort, or similar) that runs O(n log n) and is highly optimized. Bubble sort has one genuine advantage: it's stable (equal elements maintain their relative order) and it can detect an already-sorted array in O(n) time with the early-exit optimization (if no swaps were made in a pass, the array is sorted). This makes it marginally useful for nearly-sorted data, though insertion sort handles this case better. The more important lesson from bubble sort is understanding O(n²) as a performance class and recognizing it in real code. Any algorithm with nested loops where both loops iterate over the input is likely O(n²) and should trigger a review of whether a more efficient approach exists.

Code Example

// Bubble sort with early-exit optimization
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    // Each pass shrinks: last i elements are already sorted
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // swap
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted — O(n) best case
  }
  return arr;
}

console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]

// In production, just use this:
const sorted = [64, 34, 25, 12].sort((a, b) => a - b);

Why It Matters for Engineers

Bubble sort is primarily a teaching tool that illustrates sorting mechanics and O(n²) complexity. The real reason to understand it is to recognize O(n²) patterns in your own code: any time you see two nested for-loops iterating over the same collection, ask whether you've just written an accidental bubble sort variant. Many real bugs (like "find all pairs" problems solved naively) have this structure. Understanding why O(n²) is unacceptable for large inputs — 1 million elements × 1 million operations = 10^12 operations vs. n log n's ~20 million — builds the quantitative intuition for performance that separates engineers who understand complexity from those who just know the Big O notation symbols.