Algorithms/Sorting/Bubble Sort

Bubble Sort

Repeatedly swap adjacent elements that are out of order. The simplest comparison sort — O(n²) worst case, but with an early-termination optimization that makes it linear on already-sorted input.

SortingComparisonStableO(n²)

Comparisonsso far

Writesso far

Array Visualization

Adjacent swaps bubble the largest unsorted element toward the right

default comparing swapping sorted

Main arrayin-place

Arrayn = 16

109

1110

1211

1312

1413

1514

1615

✓

RecursionAll sorted — no active range.

1 / 0

Speed

Preset

n16

Early termination

bubble-sort.js

1function bubbleSort(arr) {

2 const n = arr.length;

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

4 let swapped = false; // early-termination flag

6 for (let j = 0; j < n - 1 - i; j++) {

7 if (arr[j] > arr[j + 1]) {

8 swap(arr, j, j + 1);

9 swapped = true; // a swap occurred

10 }

11 }

13 if (!swapped) break; // already sorted — bail out

14 }

15}

Algorithm Explanation

Bubble sort is the simplest comparison-based sorting algorithm. It repeatedly walks through the array, comparing each pair of adjacent elements and swapping them if they're out of order. After each full pass, the largest unsorted element has "bubbled" to the end of the array — hence the name.

⚙️ How It Works

Pass through the array from left to right. Compare each adjacent pair (arr[j], arr[j+1]).
Swap if arr[j] > arr[j+1]. Otherwise leave the pair alone.
After each pass, the largest unsorted element has bubbled to the right end. We can ignore it on subsequent passes — the unsorted region shrinks by one each iteration.
Repeat until a full pass performs no swaps (the array is sorted) — or, in the unoptimized variant, until n − 1 passes have run.

🐢 Why is it slow?

Bubble sort touches every pair on every pass. With n elements and n − 1 passes, that's O(n²) comparisons in the worst case. For arrays of size 1000, that's a million comparisons — versus ~10,000 for merge sort or quicksort. Bubble sort is mainly useful for teaching, not for production.

💡 Stable: Bubble sort uses an < comparison (strict greater-than for the swap), so equal elements never swap past each other. It's one of the few simple sorts that's natively stable.

⚖️ Bubble vs Selection vs Insertion

Bubble sort (this page)

O(n²) worst case, O(n) best (with early termination).
Stable.
In-place (O(1) extra).
Slowest of the three for random data.

Selection sort

O(n²) worst case, O(n²) best — never short-circuits.
Not stable by default.
In-place (O(1) extra).
Fewer swaps than bubble sort (≤ n − 1).

Insertion sort

O(n²) worst case, O(n) best (already sorted).
Stable.
In-place (O(1) extra).
Fastest of the three for small / nearly-sorted n.

Toggle 'Early termination' on to see how a single sorted pass can short-circuit the algorithm at the cost of an extra flag variable.