Sorting · Beginner

Selection Sort

Scan for the minimum, lock it in, repeat — the fewest writes of any comparison sort.

AverageO(n²)StableNoIn-placeYesComparisonYes

Hands on Interactive visualization

Speed

Step 0 / 0

Comparisons

Swaps

Reads

Writes

Elapsed

0.0s

Frames

Depth

0 / 0

Aux memory

0 B

Implementation Code

export function selectionSort(a: number[]): number[] {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let min = i;
    // Scan the unsorted suffix for the smallest element.
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[min]) min = j;
    }
    if (min !== i) {
      [a[i], a[min]] = [a[min], a[i]]; // single swap per pass
    }
  }
  return a;
}

Big-O Complexity

Best

O(n²)

Average

O(n²)

Worst

O(n²)

Space

O(1)

Always n(n-1)/2 comparisons regardless of input order — but at most n-1 swaps.

StableNoIn-placeYesComparisonYesRecursiveNoAdaptiveNoOnlineNo

In production When to use

Write-constrained storage

With at most n-1 swaps, it minimizes writes — relevant when writes are expensive, such as EEPROM or flash memory with limited erase cycles.

Embedded

Fixed, predictable work per input size and O(1) memory make it easy to reason about on real-time firmware where worst-case timing matters more than average speed.

Education

Cleanly demonstrates the selection strategy that underlies heap sort: heap sort is selection sort with a smarter O(log n) minimum-extraction structure.

Tiny inputs

For arrays of a few dozen elements inside a hot loop, its branch-predictable scan and minimal writes can be competitive with fancier sorts.

Interview building block

Partial selection (run k passes) is the naive answer to 'find the k smallest elements' and a stepping stone to heap- and quickselect-based answers.

Trade-offs Strengths & weaknesses

Minimal writes: at most n-1 swaps, the fewest of any in-place comparison sort.
Dead simple with no best/worst-case surprises — performance is identical on every input.
In-place, O(1) memory, no recursion.
Inner loop is a pure scan: branch-predictor and prefetcher friendly.
Easy to adapt into a partial sort (stop after k passes for the k smallest elements).

Always O(n²) comparisons — not adaptive, so even a sorted array costs full price.
Not stable in its standard form: the long-range swap can reorder equal keys.
Slower than insertion sort on average despite the same complexity class.
Cannot early-exit: it has no way to notice the array is already sorted.
The minimum-scan is inherently sequential, resisting vectorization tricks.

Intuition Mental model

Picking a starting lineup

A coach builds a lineup by repeatedly scanning the entire bench for the best remaining player and seating them in the next chair. The seated players never move again.

Scan every player still on the bench and remember the best one seen.
After the full scan — never before — swap that best player into the next open chair.
That chair is now final; nobody seated is ever reconsidered.
Repeat with a bench that shrinks by one each round.
The scan always covers the whole bench, which is why the work never shrinks below n²/2 comparisons.

Prep Interview questions

Why is selection sort not stable, and how could you make it stable?

The swap can jump the current element over an equal key further right. Stable variant: instead of swapping, remove the minimum and shift the gap closed (insert it), which costs O(n) moves per pass.

Selection sort does O(n²) comparisons but only O(n) swaps. When is that trade worth it?

When a write costs far more than a read — flash wear leveling, records with huge payloads and cheap keys, or hardware where writes invalidate caches.

What is the relationship between selection sort and heap sort?

Identical strategy — repeatedly extract the extreme element. Heap sort replaces the O(n) linear scan for the extreme with an O(log n) heap operation.

Can selection sort ever beat insertion sort?

On inputs where insertion sort degrades to many shifts (e.g. reverse-sorted) and writes dominate cost, selection's bounded swap count wins. On nearly-sorted data insertion sort wins decisively.

How would you find the k smallest elements with selection sort, and what is the cost?

Run only k outer passes: O(k·n). Compare with a size-k max-heap at O(n log k) and quickselect at expected O(n).

Watch out Common bugs

Swapping inside the scan loop

Swapping every time a smaller element is seen (instead of tracking minIndex and swapping once after the scan) still sorts, but silently turns the algorithm into an O(n²)-write variant and defeats its one selling point.

Forgetting to reset minIndex to i

Initializing minIndex to 0 (or the previous pass's value) instead of the current boundary i pulls already-placed elements back into play and corrupts the sorted prefix.

Outer loop running to n instead of n-1

The last element is in place by construction; iterating the final pass is harmless but signals a shaky grasp of the invariant — and in some variants triggers an out-of-bounds scan.

Assuming stability when sorting records

Sorting objects by key with vanilla selection sort can reorder equal keys. If callers rely on the previous order surviving (multi-key sort chains), this is a silent data bug.

One screen Cheat sheet

Find the min of the unsorted suffix, swap it to the front, advance the boundary.

Best O(n²) · Avg O(n²) · Worst O(n²) · Space O(1)

At most n-1 swaps — the write-minimal comparison sort.
Comparisons are fixed at n(n-1)/2: no adaptivity, no early exit.
Not stable: the long-range swap reorders equal keys.
One swap per pass, after the scan completes — never mid-scan.
Same extract-the-extreme strategy as heap sort, minus the heap.

Pick whenWrites are dramatically more expensive than reads, or you need predictable fixed-cost sorting of tiny arrays.

Avoid whenData is large, nearly sorted, or stability matters — insertion sort or a real O(n log n) sort wins everywhere else.

Implementation Code

export function selectionSort(a: number[]): number[] {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let min = i;
    // Scan the unsorted suffix for the smallest element.
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[min]) min = j;
    }
    if (min !== i) {
      [a[i], a[min]] = [a[min], a[i]]; // single swap per pass
    }
  }
  return a;
}

In production When to use

Write-constrained storage

With at most n-1 swaps, it minimizes writes — relevant when writes are expensive, such as EEPROM or flash memory with limited erase cycles.

Embedded

Fixed, predictable work per input size and O(1) memory make it easy to reason about on real-time firmware where worst-case timing matters more than average speed.

Education

Cleanly demonstrates the selection strategy that underlies heap sort: heap sort is selection sort with a smarter O(log n) minimum-extraction structure.

Tiny inputs

For arrays of a few dozen elements inside a hot loop, its branch-predictable scan and minimal writes can be competitive with fancier sorts.

Interview building block

Partial selection (run k passes) is the naive answer to 'find the k smallest elements' and a stepping stone to heap- and quickselect-based answers.

Trade-offs Strengths & weaknesses

Minimal writes: at most n-1 swaps, the fewest of any in-place comparison sort.
Dead simple with no best/worst-case surprises — performance is identical on every input.
In-place, O(1) memory, no recursion.
Inner loop is a pure scan: branch-predictor and prefetcher friendly.
Easy to adapt into a partial sort (stop after k passes for the k smallest elements).

Always O(n²) comparisons — not adaptive, so even a sorted array costs full price.
Not stable in its standard form: the long-range swap can reorder equal keys.
Slower than insertion sort on average despite the same complexity class.
Cannot early-exit: it has no way to notice the array is already sorted.
The minimum-scan is inherently sequential, resisting vectorization tricks.

Intuition Mental model

Picking a starting lineup

A coach builds a lineup by repeatedly scanning the entire bench for the best remaining player and seating them in the next chair. The seated players never move again.

Scan every player still on the bench and remember the best one seen.
After the full scan — never before — swap that best player into the next open chair.
That chair is now final; nobody seated is ever reconsidered.
Repeat with a bench that shrinks by one each round.
The scan always covers the whole bench, which is why the work never shrinks below n²/2 comparisons.

Prep Interview questions

Why is selection sort not stable, and how could you make it stable?

The swap can jump the current element over an equal key further right. Stable variant: instead of swapping, remove the minimum and shift the gap closed (insert it), which costs O(n) moves per pass.

Selection sort does O(n²) comparisons but only O(n) swaps. When is that trade worth it?

When a write costs far more than a read — flash wear leveling, records with huge payloads and cheap keys, or hardware where writes invalidate caches.

What is the relationship between selection sort and heap sort?

Identical strategy — repeatedly extract the extreme element. Heap sort replaces the O(n) linear scan for the extreme with an O(log n) heap operation.

Can selection sort ever beat insertion sort?

On inputs where insertion sort degrades to many shifts (e.g. reverse-sorted) and writes dominate cost, selection's bounded swap count wins. On nearly-sorted data insertion sort wins decisively.

How would you find the k smallest elements with selection sort, and what is the cost?

Run only k outer passes: O(k·n). Compare with a size-k max-heap at O(n log k) and quickselect at expected O(n).

Watch out Common bugs

Swapping inside the scan loop

Forgetting to reset minIndex to i

Initializing minIndex to 0 (or the previous pass's value) instead of the current boundary i pulls already-placed elements back into play and corrupts the sorted prefix.

Outer loop running to n instead of n-1

The last element is in place by construction; iterating the final pass is harmless but signals a shaky grasp of the invariant — and in some variants triggers an out-of-bounds scan.

Assuming stability when sorting records

Sorting objects by key with vanilla selection sort can reorder equal keys. If callers rely on the previous order surviving (multi-key sort chains), this is a silent data bug.

One screen Cheat sheet

Find the min of the unsorted suffix, swap it to the front, advance the boundary.

Best O(n²) · Avg O(n²) · Worst O(n²) · Space O(1)

At most n-1 swaps — the write-minimal comparison sort.
Comparisons are fixed at n(n-1)/2: no adaptivity, no early exit.
Not stable: the long-range swap reorders equal keys.
One swap per pass, after the scan completes — never mid-scan.
Same extract-the-extreme strategy as heap sort, minus the heap.

Pick whenWrites are dramatically more expensive than reads, or you need predictable fixed-cost sorting of tiny arrays.

Avoid whenData is large, nearly sorted, or stability matters — insertion sort or a real O(n log n) sort wins everywhere else.