How does BubbleSort work?

AlgorithmsJunior~2 min read

Short answer

Bubble Sort repeatedly passes through the array, comparing adjacent elements and swapping them if they are in the wrong order. On each pass, the "largest" of the remaining elements bubbles up to the end of the array. Passes repeat until no swap is made. Complexity is O(n²) in the average and worst cases, O(n) in the best case (with an early exit), memory is O(1), and the algorithm is stable and runs in place.

Detailed breakdown

Algorithm idea

Go left to right through the array and compare adjacent elements.
If a pair is in the wrong order, swap the elements.
By the end of the pass, the maximum element "bubbles" to the end of the array (into its final place).
Repeat new passes, ignoring the already sorted tail, until a pass makes no swaps.

Invariant: after the i-th full pass, the last i elements are in their final places.

Step-by-step example

Array: [5, 1, 4, 2, 8]

Pass 1:
- compare 5 and 1 → 5>1, swap → [1, 5, 4, 2, 8]
- compare 5 and 4 → 5>4, swap → [1, 4, 5, 2, 8]
- compare 5 and 2 → 5>2, swap → [1, 4, 2, 5, 8]
- compare 5 and 8 → 5≤8, no swap → [1, 4, 2, 5, 8]
Tail: 8 is in place.

Pass 2 (excluding the last element):
- 1 and 4 → ok
- 4 and 2 → swap → [1, 2, 4, 5, 8]
- 4 and 5 → ok
Tail: 5, 8 are in place.

Pass 3:
- 1 and 2 → ok
- 2 and 4 → ok
No swaps → early exit. Result: [1, 2, 4, 5, 8]

Pseudocode

bubbleSort(A):
  n = length(A)
  for i from 0 to n-2:
    swapped = false
    for j from 0 to n-2-i:
      if A[j] > A[j+1]:
        swap A[j], A[j+1]
        swapped = true
    if not swapped:
      break  // early exit, the array is already sorted
  return A

Implementation (JavaScript)

// Basic version (returns a new array)
function bubbleSort(arr) {
  const a = arr.slice();
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
      }
    }
  }
  return a;
}

// Optimized version: early exit + boundary at the last swap
function bubbleSortOptimized(arr) {
  const a = arr.slice();
  let n = a.length;
  while (n > 1) {
    let newN = 0; // position of the last swap
    for (let j = 0; j < n - 1; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        newN = j + 1;
      }
    }
    if (newN === 0) break; // already sorted
    n = newN; // the tail after newN is already sorted
  }
  return a;
}

// Two-way version (Cocktail Shaker Sort)
function cocktailShakerSort(arr) {
  const a = arr.slice();
  let start = 0;
  let end = a.length - 1;
  let swapped = true;
  while (swapped) {
    swapped = false;
    for (let i = start; i < end; i++) {
      if (a[i] > a[i + 1]) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    if (!swapped) break;
    swapped = false;
    end--;
    for (let i = end; i > start; i--) {
      if (a[i - 1] > a[i]) {
        [a[i - 1], a[i]] = [a[i], a[i - 1]];
        swapped = true;
      }
    }
    start++;
  }
  return a;
}

// Example
console.log(bubbleSort([5, 1, 4, 2, 8]));            // [1, 2, 4, 5, 8]
console.log(bubbleSortOptimized([5, 1, 4, 2, 8]));   // [1, 2, 4, 5, 8]
console.log(cocktailShakerSort([5, 1, 4, 2, 8]));    // [1, 2, 4, 5, 8]

Complexity and properties

Time: O(n²) in the average and worst cases; O(n) in the best case (if the array is already sorted and there is an early exit).
Memory: O(1) additional (in-place), if we sort the original array.
Stability: a stable sort (preserves the relative order of equal elements).
Number of comparisons: ~n(n-1)/2 in the worst case; the number of swaps is of the same order.

When to use (and when not to)

Use it for: very small arrays, nearly sorted data, educational purposes, when stability and a simple implementation are needed.
Avoid it for: medium and large amounts of data - O(n log n) algorithms are preferable (for example, merge sort, quicksort, heap sort).

Optimizations

Early exit: if a pass makes no swaps at all, stop.
Last-swap boundary: after the position of the last swap, the tail is already sorted, so the range of the next pass is shortened.
Two-way pass (Cocktail Shaker): speeds things up on nearly sorted data by moving large elements right and small elements left within a single cycle.

Frequent mistakes

Incorrect inner loop boundaries (forgetting -i, losing the tail optimization).
No early exit - unnecessary passes over an already sorted array.
Accidental loss of stability when trying to "speed up" comparisons without a real need.

Brief comparison

Insertion Sort: also O(n²), but faster than Bubble Sort on nearly sorted data and has fewer swap operations.
Selection Sort: O(n²), but performs a minimal number of swaps; unstable; usually faster than Bubble Sort in terms of constants, but worse on nearly sorted data.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.