Introduction

Bubble sort is a comparison-based sorting algorithm where adjacent elements are repeatedly compared and swapped if they are out of order.

Bubble Sort Mechanics

Bubble sort repeatedly examines adjacent values and swaps them when they are out of order. These swaps move the largest unsorted value toward the end of the array.

Implementing Bubble Sort

Overview

Bubble sort repeatedly compares adjacent elements in an array. If they are in the wrong order, it swaps them. After each pass, the unsorted region becomes smaller.

function bubbleSort(array) {
  for (let end = array.length - 1; end > 0; end--) {
    for (let index = 0; index < end; index++) {
      const nextIndex = index + 1;

      if (array[index] > array[nextIndex]) {
        const temporary = array[index];
        array[index] = array[nextIndex];
        array[nextIndex] = temporary;
      }
    }
  }

  return array;
}

How the loops work

• The outer loop controls the end of the unsorted region. It starts at the last array index and moves left after each pass.
• The inner loop visits adjacent pairs from the beginning of the array up to that boundary.
• When the left value is greater than the right value, the values are swapped.
• As the outer loop moves left, the inner loop processes a progressively smaller unsorted region.

For example, the comparison array[index] > array[nextIndex] checks whether two adjacent values are out of order. The temporary variable preserves one value while the two array positions exchange values.

Swap logic

A swap exchanges the value at the current position with the smallest value found by the inner loop.

If smallestIndex is already i, the current value is already the smallest remaining value, so no meaningful move is needed (avoiding a redundant self-swap).

Optimizing Bubble Sort

The optimization

Bubble sort repeatedly makes passes through the data and swaps items when needed. A simple optimization is to track whether each pass made any swaps.

• If the pass made at least one swap, continue.
• If a complete pass made no swaps, stop immediately.

A pass with no swaps means the optimization has found that no changes were needed during that pass.

Optimized Implementation

function bubbleSort(array) {
  for (let end = array.length - 1; end > 0; end--) {
    let hasSwapped = false;

    for (let index = 0; index < end; index++) {
      const nextIndex = index + 1;

      if (array[index] > array[nextIndex]) {
        const temporary = array[index];
        array[index] = array[nextIndex];
        array[nextIndex] = temporary;
        hasSwapped = true;
      }
    }

    // If no swaps occurred in this pass, the array is already sorted
    if (!hasSwapped) break;
  }

  return array;
}

Performance comparison

Without the early-stop check, bubble sort continues through its passes even when the data is already ordered. With the check, already sorted data can finish after a single pass, making the work linear in the amount of data.

The same optimization is useful when data is nearly sorted, because bubble sort can stop as soon as a complete pass makes no swaps.

Key Takeaways

• Adjacent Comparisons & Swaps: Bubble sort repeatedly examines adjacent pairs and swaps them if they are in the wrong order.
• Bubbling to the End: Each pass guarantees that the largest unsorted element moves to its correct sorted position at the end of the array.
• Shrinking Unsorted Boundary: An outer loop tracks the decreasing unsorted region, preventing redundant comparisons on already sorted elements.
• Early-Stop Optimization: By checking whether any swaps occurred during a pass, the algorithm can terminate early when the array is already sorted.
• Complexity Profile: General and worst-case time complexity is $O(n^2)$, best-case time complexity with optimization is $O(n)$, and auxiliary space complexity is $O(1)$ (in-place).