Bubble Sort

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Bubble sort

Loading interactive demo…

Bubble sort sweeps the array left to right comparing neighbors and swapping a pair whenever the left one is bigger. Each sweep carries the largest remaining bar to the end of the unsorted region, and the sort stops after a sweep with no swaps. Take the tour, or press and explore. Legend:

The panel beside the stage is the real BubbleSort class from the published library executing in your browser, with the current line highlighted.

The left bar of the pair being compared (always the brightest bar).
Its right-hand neighbor. The bracket points at the pair.
The sorted tail: retired maximums in their final slots.
Every bar, once the whole array is sorted.

Every sweep costs one comparison per pair in the unsorted region, so a shuffled array takes about n squared over two comparisons. Drag the bars sorted and watch the flag end the sort after a single sweep.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Each sweep compares every neighboring pair in the unsorted region, and the region shrinks by one slot per sweep, so a full run costs

(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2} = O(n^2)

comparisons. Swaps are easier to count: every swap fixes exactly one inversion (a pair in the wrong order), so the swap count equals the number of inversions in the input, from $0$ on sorted data up to $n(n-1)/2$ on reversed data, and $O(n^2)$ on average. The swapped flag gives the best case: an already sorted array costs a single sweep of $n-1$ comparisons, $O(n)$ . Bubble sort is stable, because the strict > never swaps equal neighbors, and in place, needing only one temporary and two indices.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

end shrinks by one per sweep: the slot it just left holds a retired maximum, so the inner loop never revisits it.
The swapped flag is the early exit. One full sweep with no swap proves every neighbor is in order, and that means the whole array is.
The comparison is a strict >, so equal neighbors never trade places: that is what makes the sort stable.
A swap is three assignments through held, the only extra memory the algorithm uses.
[...input] copies the input first: the class returns a sorted copy and never mutates what it was given.
Each tracer snapshot is taken before the swap it announces, so the stage shows the pair as it was when the decision was made.

Bubble sort is the sort everyone reinvents: compare each pair of neighbors, swap the ones out of order, and repeat until a pass makes no swaps. It was described for early business computers in 1956, when Edward Friend analyzed it as sorting by exchange, picked up its name in Kenneth Iverson's 1962 book A Programming Language, and has served ever since as the first idea every other sort improves on.

1956Edward H. Friend - Publishes 'Sorting on Electronic Computer Systems' in the Journal of the ACM, the earliest known description of the algorithm, analyzed there as sorting by exchange.source
1962Kenneth Iverson - Uses the name 'bubble sort' in A Programming Language, the earliest use of the term in print that later historians could find.source
1973Donald Knuth - The Art of Computer Programming Vol. 3 analyzes it and concludes it has nothing to recommend it except a catchy name and some interesting theoretical problems.source
2003Owen Astrachan - Presents 'Bubble Sort: An Archaeological Algorithmic Analysis' at SIGCSE, tracing why the sort stays in every textbook despite decades of warnings.source

Used today

The first sort in every course - A two-line idea that introduces comparisons, swaps, nested loops, and invariants before any faster method.
Nearly-sorted repair - With the early-exit flag, a sorted array costs one pass, so a few out-of-place items are fixed cheaply.
Sorting networks - Odd-even transposition sort, its parallel cousin, runs one value per processor with only neighbor links.

n12

comparisons: 0
swaps: 0
passes: 0

bubble-sort.ts

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Bubble sort: sweep the unsorted prefix left to right, swapping each * pair of neighbors that is out of order. Every sweep carries the * largest remaining value to the end of the prefix, and a sweep with * no swaps proves the array sorted, so the sort stops early. * * Time: O(n²) worst and average, O(n) when already sorted. Space: O(1) extra. */export class BubbleSort implements SortAlgorithm {  readonly name = "bubble-sort";  constructor(private readonly tracer?: Tracer) {}  sort(input: readonly number[]): number[] {    const a = [...input];    const array = [...input];    for (let end = a.length - 1; end >= 1; end--) {    for (let unsortedEnd = array.length - 1; unsortedEnd >= 1; unsortedEnd--) {      let swapped = false;      for (let j = 0; j < end; j++) {      for (let cursor = 0; cursor < unsortedEnd; cursor++) {        // ▸ compare this pair of neighbors        this.tracer?.emit("compare", { end, j, array: [...a] });        this.tracer?.emit("compare", { unsortedEnd, cursor, array: [...array] });        if (a[j]! > a[j + 1]!) {        if (array[cursor]! > array[cursor + 1]!) {          // ▸ the left one is bigger, swap them          this.tracer?.emit("swap", { end, j, array: [...a] });          this.tracer?.emit("swap", { unsortedEnd, cursor, array: [...array] });          const held = a[j]!;          const held = array[cursor]!;          a[j] = a[j + 1]!;          array[cursor] = array[cursor + 1]!;          a[j + 1] = held;          array[cursor + 1] = held;          swapped = true;        }      }      // ▸ the sweep is over, its largest value is in place      this.tracer?.emit("pass-done", { end, swapped, array: [...a] });      this.tracer?.emit("pass-done", { unsortedEnd, swapped, array: [...array] });      if (!swapped) break;    }    return a;    return array;  }}

The array before sorting: bubble sort will sweep it left to right, comparing each bar with its right-hand neighbor.

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Bubble sort: sweep the unsorted prefix left to right, swapping each * pair of neighbors that is out of order. Every sweep carries the * largest remaining value to the end of the prefix, and a sweep with * no swaps proves the array sorted, so the sort stops early. * * Time: O(n²) worst and average, O(n) when already sorted. Space: O(1) extra. */export class BubbleSort implements SortAlgorithm { readonly name = "bubble-sort"; constructor(private readonly tracer?: Tracer) {} sort(input: readonly number[]): number[] { const a = [...input]; const array = [...input]; for (let end = a.length - 1; end >= 1; end--) { for (let unsortedEnd = array.length - 1; unsortedEnd >= 1; unsortedEnd--) { let swapped = false; for (let j = 0; j < end; j++) { for (let cursor = 0; cursor < unsortedEnd; cursor++) { // ▸ compare this pair of neighbors this.tracer?.emit("compare", { end, j, array: [...a] }); this.tracer?.emit("compare", { unsortedEnd, cursor, array: [...array] }); if (a[j]! > a[j + 1]!) { if (array[cursor]! > array[cursor + 1]!) { // ▸ the left one is bigger, swap them this.tracer?.emit("swap", { end, j, array: [...a] }); this.tracer?.emit("swap", { unsortedEnd, cursor, array: [...array] }); const held = a[j]!; const held = array[cursor]!; a[j] = a[j + 1]!; array[cursor] = array[cursor + 1]!; a[j + 1] = held; array[cursor + 1] = held; swapped = true; } } // ▸ the sweep is over, its largest value is in place this.tracer?.emit("pass-done", { end, swapped, array: [...a] }); this.tracer?.emit("pass-done", { unsortedEnd, swapped, array: [...array] }); if (!swapped) break; } return a; return array; }}