SortingAlgorithmaka minimum selection sort

Selection Sort

Repeatedly select the minimum of the unsorted suffix and swap it into place; exactly n−1 swaps.

▶ VisualizePattern: Two PointersPractice (1)
Progress

Overview

Selection sort grows a sorted prefix one element at a time: scan the unsorted suffix for its minimum and swap it to the front of the suffix. It always does n(n-1)/2 comparisons regardless of input — it is not adaptive — but at most n - 1 swaps, the fewest writes of any general comparison sort.

It is in-place and, in its usual swap-based form, not stable (swapping the minimum into position can jump an equal element over another). Its niche is when writes are far more expensive than reads, e.g. flash memory with limited write cycles or huge records where moving is costly.

comparisonO(n²)in-placeunstableminimal writes

Intuition

A mental model before the formal terms.

Sorting a hand of cards by repeatedly scanning for the smallest card you have not placed yet and moving it to the next slot on the left. You look at every remaining card each time, but you only ever move one card per round.

How it works

  1. For i = 0 … n - 2, set minIdx = i.
  2. Scan j = i + 1 … n - 1; if a[j] < a[minIdx], set minIdx = j.
  3. Swap a[i] with a[minIdx].
  4. After the loop, the whole array is the sorted prefix.

Why it works

Invariant: after iteration i, a[0..i] contains the i + 1 smallest elements in sorted order, and every element of a[i+1..] is ≥ a[i].

The scan finds the true minimum of the suffix, which is exactly the next element in sorted order; placing it at i extends the invariant.

Recognition

How to tell a problem wants this.

  • The problem restricts the number of writes/swaps rather than comparisons.
  • You need a predictable, data-independent running time (e.g. constant-time side-channel resistance on small arrays).
  • Asked to explain why a sort is unstable and how to fix it (shift instead of swap at O(n²) writes).
“sorted array” → Two Pointers

Interactive visualization

Play, step, change the input. ← → and space work too.

29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
1/51Start with 8 elements. Each pass selects the smallest remaining value and places it at the front of the unsorted part.
Current minimumComparingSwappedIn final position
PseudocodeLearn Selection Sort →
1for i in 0 .. n-2:
2  minIdx = i
3  for j in i+1 .. n-1:
4    if a[j] < a[minIdx]:
5      minIdx = j
6  swap(a[i], a[minIdx])
Complexity
best O(n²)
avg O(n²)
worst O(n²)
space O(1)
Speed

Pseudocode

1for i from 0 to n - 2:
2  minIdx = i
3  for j from i + 1 to n - 1:
4    if a[j] < a[minIdx]: minIdx = j
5  swap(a[i], a[minIdx])

Implementations

1def selection_sort(a: list[int]) -> None:
21 · Setup
3    n = len(a)
42 · Grow the sorted prefix one slot at a time
5    for i in range(n - 1):
63 · Find the minimum of the unsorted suffix
7        min_idx = i
8        for j in range(i + 1, n):
9            if a[j] < a[min_idx]:
10                min_idx = j
114 · Swap it into place (at most one write pair per pass)
12        if min_idx != i:
13            a[i], a[min_idx] = a[min_idx], a[i]
Walkthrough
  1. range(i + 1, n) scans the unsorted suffix; on n <= 1 the outer range(n - 1) is empty.
  2. Tracking min_idx (not the value) lets the tuple swap target the slot directly.
  3. One swap per pass — the minimum-writes property.
  4. No early exit: comparisons are always n(n-1)/2.
Complexity (this implementation)
time O(n²) in all cases · space O(1)

min(range(i, n), key=a.__getitem__) does the scan in C but is still O(n) per pass.

Language notes
  • min(range(i, n), key=a.__getitem__) returns the index of the minimum in one expression.
  • Python list.sort() is stable; selection sort is not — use sorted(a, key=...) for real work.
  • The tuple swap is atomic from the reader's point of view; no temp variable needed.
Common mistakes in this language
  • Using a.index(min(a[i:])) — the slice copies and index finds the first match in the whole list, not the suffix.
  • Swapping inside the inner loop.
  • Assuming stability.
Language differences that matter here
  • Swap-based selection sort is unstable in every language; the stable variant (shift instead of swap) costs O(n²) writes and loses the minimal-writes advantage.
  • C++ std::min_element / std::iter_swap and Python min(range, key=) express the inner scan with library calls; JS/TS have no index-returning min and need the manual loop.
  • Library sorts are stable in Python and JS (since ES2019) but std::sort is not — use std::stable_sort when equal keys must keep order.
  • Numeric [10, 2, 5].sort() in JS/TS sorts as strings; C++ and Python compare numbers.

Complexity

Best
O(n²)
Average
O(n²)
Worst
O(n²)
Space
O(1)

Always n(n−1)/2 comparisons; at most n−1 swaps. In-place, not stable, not adaptive.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Writes are expensive and must be minimized (EEPROM/flash, large records moved by value).
  • Very small arrays where simplicity matters and input order is arbitrary.
  • When a data-independent number of comparisons is desired.
Avoid it when
  • Nearly sorted input — selection sort does not benefit; Insertion Sort runs in O(n).
  • Stability is required (use insertion sort or Merge Sort).
  • Anything beyond a few hundred elements.

Alternatives

Insertion SortHeap SortBubble Sort

Common mistakes

  • Believing it is stable; [2a, 2b, 1] becomes [1, 2b, 2a].
  • Swapping inside the inner loop whenever a smaller element is seen — that is a different, slower algorithm with O(n²) swaps.
  • Running the outer loop to n - 1 inclusive (harmless but wasteful).

Interview patterns

  • Contrast with Heap Sort: heap sort is selection sort with an O(log n) "find minimum" instead of O(n).
  • Make it stable by inserting the minimum via shifting rather than swapping.
  • Bidirectional (double-ended) selection sort picks min and max each pass.
Interview questions on this
Mock interviews

Example problems

Kth Largest Element in an Arraymedium