Selection Sort

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

Selection sort

Loading interactive demo…

Selection sort finds the smallest bar in the unsorted region and swaps it into that region's first slot, growing a sorted prefix one final position per pass. Take the tour, or press and explore. Legend:

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

The current minimum candidate: the smallest bar the scan has seen so far in this pass (always the brightest bar).
The bar being checked against it, or, once the scan is over, the open slot the minimum is about to fill. The bracket points at the pair.
The sorted prefix: slots already holding their final value.
Every bar, once the whole array is sorted.

Each pass scans every remaining bar, so the comparison count never depends on the input order: drag the bars sorted or reversed and only the swap count changes.

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

Selection sort is the careful clerk's strategy: scan the pile for the smallest item, set it aside, scan again. It appears in the earliest surveys of sorting for electronic computers, where it stood out for touching the data very little, one exchange per pass. Its lasting legacy is an idea rather than the code: replace the linear scan with a faster way of finding the minimum and the same skeleton becomes heapsort.

1956Edward H. Friend - Publishes 'Sorting on Electronic Computer Systems' in the Journal of the ACM, an early survey of sorting methods that already includes sorting by selection.source
1964J. W. J. Williams - Heapsort keeps the selection skeleton, repeatedly moving the extreme element to its final slot, but finds it with a heap instead of a scan.source
1973Donald Knuth - The Art of Computer Programming Vol. 3 files the method under 'Sorting by Selection' (section 5.2.3) as straight selection, next to its tree-based descendants.source
1981Ronald Baecker - The animated film Sorting Out Sorting races straight selection against tree selection and heapsort on screen, an early landmark of algorithm animation.source

Used today

Write-limited memory - At most n - 1 swaps: where writes cost far more than reads, as with EEPROM or flash, a scan beats a move. Cycle sort pushes the idea to the minimum number of writes.
Tiny code - Two nested loops, one swap, no recursion and no extra memory: a natural fit for small firmware and for a first sorting lesson.
The seed of heapsort - Replace the linear scan with a heap or a tournament tree and the same skeleton finds each minimum in log n time.

n12

comparisons: 0
swaps: 0
passes: 0

selection-sort.ts

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Selection sort: scan the unsorted region for its minimum, swap it * into the first unsorted slot, and repeat, growing a sorted prefix * one final position per pass. Every pass scans everything that is * left, so the work never depends on the input order. * * Time: O(n²) always. Space: O(1) extra. */export class SelectionSort implements SortAlgorithm {  readonly name = "selection-sort";  constructor(private readonly tracer?: Tracer) {}  sort(input: readonly number[]): number[] {    const a = [...input];    const array = [...input];    const n = a.length;    const n = array.length;    for (let i = 0; i < n - 1; i++) {      let min = i;      let smallest = i;      for (let j = i + 1; j < n; j++) {      for (let cursor = i + 1; cursor < n; cursor++) {        // ▸ is this bar smaller than the smallest seen so far?        this.tracer?.emit("compare", { i, j, min, array: [...a] });        this.tracer?.emit("compare", { i, cursor, smallest, array: [...array] });        if (a[j]! < a[min]!) min = j;        if (array[cursor]! < array[smallest]!) smallest = cursor;      }      // ▸ the scan is over: min points at the smallest bar left      this.tracer?.emit("select-min", { i, min, array: [...a] });      this.tracer?.emit("select-min", { i, smallest, array: [...array] });      if (min !== i) {      if (smallest !== i) {        // ▸ swap the smallest bar into the first unsorted slot        this.tracer?.emit("swap", { i, min, array: [...a] });        this.tracer?.emit("swap", { i, smallest, array: [...array] });        const held = a[i]!;        const held = array[i]!;        a[i] = a[min]!;        array[i] = array[smallest]!;        a[min] = held;        array[smallest] = held;      }    }    return a;    return array;  }}

The array before sorting. Each pass will fill one more slot from the left.

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Selection sort: scan the unsorted region for its minimum, swap it * into the first unsorted slot, and repeat, growing a sorted prefix * one final position per pass. Every pass scans everything that is * left, so the work never depends on the input order. * * Time: O(n²) always. Space: O(1) extra. */export class SelectionSort implements SortAlgorithm { readonly name = "selection-sort"; constructor(private readonly tracer?: Tracer) {} sort(input: readonly number[]): number[] { const a = [...input]; const array = [...input]; const n = a.length; const n = array.length; for (let i = 0; i < n - 1; i++) { let min = i; let smallest = i; for (let j = i + 1; j < n; j++) { for (let cursor = i + 1; cursor < n; cursor++) { // ▸ is this bar smaller than the smallest seen so far? this.tracer?.emit("compare", { i, j, min, array: [...a] }); this.tracer?.emit("compare", { i, cursor, smallest, array: [...array] }); if (a[j]! < a[min]!) min = j; if (array[cursor]! < array[smallest]!) smallest = cursor; } // ▸ the scan is over: min points at the smallest bar left this.tracer?.emit("select-min", { i, min, array: [...a] }); this.tracer?.emit("select-min", { i, smallest, array: [...array] }); if (min !== i) { if (smallest !== i) { // ▸ swap the smallest bar into the first unsorted slot this.tracer?.emit("swap", { i, min, array: [...a] }); this.tracer?.emit("swap", { i, smallest, array: [...array] }); const held = a[i]!; const held = array[i]!; a[i] = a[min]!; array[i] = array[smallest]!; a[min] = held; array[smallest] = held; } } return a; return array; }}