Bubble Sort

Introduction

Bubble Sort is the simplest sorting algorithm. It repeatedly steps through the array, compares adjacent elements, and swaps them if they’re in the wrong order. The largest unsorted element “bubbles up” to its correct position on each pass — like air bubbles rising to the surface of water.

Nobody uses Bubble Sort in production (it’s too slow), but it’s worth understanding because it’s often the first sorting algorithm taught, it appears in interviews as a baseline comparison, and optimizing it teaches useful concepts. You should know Arrays and Big-O Notation before reading this.

How it works

[5, 3, 8, 1, 2]

Pass 1:
[5, 3, 8, 1, 2]  → swap 5,3 → [3, 5, 8, 1, 2]
[3, 5, 8, 1, 2]  → 5<8, skip → [3, 5, 8, 1, 2]
[3, 5, 8, 1, 2]  → swap 8,1 → [3, 5, 1, 8, 2]
[3, 5, 1, 8, 2]  → swap 8,2 → [3, 5, 1, 2, 8]  ← 8 is in place

Pass 2:
[3, 5, 1, 2, 8]  → 3<5, skip
[3, 5, 1, 2, 8]  → swap 5,1 → [3, 1, 5, 2, 8]
[3, 1, 5, 2, 8]  → swap 5,2 → [3, 1, 2, 5, 8]  ← 5 is in place

Pass 3:
[3, 1, 2, 5, 8]  → swap 3,1 → [1, 3, 2, 5, 8]
[1, 3, 2, 5, 8]  → swap 3,2 → [1, 2, 3, 5, 8]  ← 3 is in place

Done: [1, 2, 3, 5, 8]

After each pass, the next largest element is in its final position, so the unsorted portion shrinks by one.

Implementation

function bubbleSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let swapped = false;

    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]];
        swapped = true;
      }
    }

    if (!swapped) break; // already sorted
  }
  return arr;
}

console.log(bubbleSort([5, 3, 8, 1, 2]));  // [1, 2, 3, 5, 8]

def bubble_sort(arr):
    n = len(arr)

    for i in range(n - 1):
        swapped = False

        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        if not swapped:
            break

    return arr

print(bubble_sort([5, 3, 8, 1, 2]))  # [1, 2, 3, 5, 8]

public static int[] bubbleSort(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;
    }
    return arr;
}

Two optimizations are built in:

1. n - 1 - i — the inner loop shrinks each pass since the end is already sorted
2. swapped flag — if no swaps happen in a pass, the array is sorted and we stop early

Complexity analysis

Space: O(1) — sorts in place.

Stable: Yes — equal elements keep their relative order because we only swap when strictly greater.

When would you actually use it?

Almost never. But there are two narrow cases:

• Tiny arrays (under ~10 elements) — the simplicity and low overhead can beat fancier algorithms
• Nearly sorted data — the early termination makes it O(n) when only a few elements are out of place

In interviews, Bubble Sort is useful as a baseline to compare against. If someone asks “why is Quick Sort better?”, you should be able to explain the O(n²) vs O(n log n) difference concretely.

Practice problems

1. Sort an array using Bubble Sort
2. Count the number of swaps needed to sort an array
3. Sort a linked list using Bubble Sort logic