Home/Sorting/Bubble sort
Search algorithmsCTRL K

Bubble sort

· exchange sort · adjacent swaps
/sorting/bubble-sort
COMPARISONS
0
n(n−1)/2 at worst
SWAPS
0
one per inversion
PASS
0/ 23
largest value bubbles to the end
IN PLACE
0/ 24
final positions so far
UNSORTED
24
still to settle
comparingswappedin place
n = 24 · seed 7 · 453 steps
step 0 / 452
Size24
bubble_sort.ts
1
function bubbleSort(array: number[]) {
2
  for (let end = array.length - 1; end > 0; end--) {
3
    let swapped = false;
4
    for (let j = 0; j < end; j++) {
5
      if (array[j] > array[j + 1]) {
6
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
7
        swapped = true;
8
      }
9
    }
10
    if (!swapped) break;
11
  }
12
}
CURRENT STEP
line 1

Start: 24 values in random order. Each pass bubbles the largest unsorted value to the end.

// how it works

Understanding Bubble sort

bubble sort · the first one everyone learns · and why nobody ships it
01

The idea

Bubble sort walks the array comparing each pair of neighbours and swapping them when they are out of order. After one full pass the largest value has bubbled to the end, so the next pass can stop one position earlier. The sorted suffix grows by one on every pass.

The early exit is the one optimisation worth having: if a pass makes no swap, the array is already sorted and the loop ends. On nearly sorted input that turns n² work into a single pass; on random input it changes nothing.

02

The four stages

1
comparearray[j] against array[j + 1]
2
swapwhen the left one is larger
3
settlethe pass ends, array[end] is final
4
exitno swap in a pass: done
03

Complexity

best
O(n)already sorted, one pass with the early exit
average
O(n²)≈ n²/2 comparisons, n²/4 swaps
worst
O(n²)reversed input, every pair swaps
space
O(1)in place, one temporary
04

Versus its siblings

COMPARISONS AT N = 1 000
bubble
499,500
cocktail
470,000
insertion
250,000
quick
13,900
merge
8,700
random input · bubble sort with early exit still does n²/2 here
05

Pseudocode

BUBBLESORT(array)
  for end ← n − 1 down to 1
    swapped ← false
    for j ← 0 to end − 1
      if array[j] > array[j + 1]: swap array[j], array[j + 1]; swapped ← true
    if not swapped: return
06

When to use

Teaching: it is the clearest picture of what a comparison sort does, and the animation everyone remembers.
Tiny or nearly sorted arrays where the early exit finishes in one pass and the code fits in five lines.
07

Pitfalls

It is the slowest of the quadratic sorts in practice: insertion sort does the same comparisons with far fewer writes.
Without the swapped flag it always does n − 1 passes, even on sorted input.
Small values move only one position per pass (the turtles); cocktail shaker and comb sort exist to fix that.
08

History

Exchange sorts were described as early as 1956 by Edward Friend, and the name bubble sort was popularised by Kenneth Iverson in 1962. Donald Knuth wrote in 1973 that it "seems to have nothing to recommend it, except a catchy name", and it has been the first sort taught in most courses ever since.

Back to Sorting