Selection Sort Visualizer

Selection sort has one distinguishing property, and it is worth knowing before anything else: it performs at most n−1 swaps, fewer than any other common comparison sort. Everything else about it is mediocre. But that single property is the reason it still appears in real systems, decades after it stopped being a reasonable default.

The strategy is exactly what the name says. Look through the unsorted part of the array, select the smallest value you find, and put it where it belongs. Repeat with what is left.

What is selection sort?

Selection sort divides the array into two regions: a sorted prefix on the left that grows by one element per pass, and an unsorted suffix on the right that shrinks. Each pass scans the entire unsorted suffix, finds the minimum, and swaps it with the first unsorted position.

The crucial difference from bubble sort is *when* the movement happens. Bubble sort moves elements continuously, swapping at every out-of-order pair it meets. Selection sort does no movement at all while scanning — it only remembers an index — and then performs a single decisive swap at the end of the pass. All that scanning produces one write.

That asymmetry between comparisons and writes is the entire character of the algorithm. It compares as much as the worst sorts do, and writes as little as it is possible to write.

Why it works

The invariant is short: after pass k, the first k positions hold the k smallest values of the array, in sorted order. Pass k+1 scans everything that remains, which by the invariant contains only values greater than or equal to those already placed, and selects the smallest of them. That value therefore belongs at position k+1, and putting it there extends the invariant by one.

Termination is trivial — the unsorted region shrinks by exactly one element per pass, so after n−1 passes only one element remains, and it must be the largest. Nothing needs to be checked.

Notice what the proof does *not* require: it never assumes anything about the order of the unsorted suffix. This is why selection sort's behaviour never varies with the input, and why it has no best case worth speaking of.

Step-by-step walkthrough

Take [64, 25, 12, 22, 11]. Watch how much scanning produces how little movement.

1. Pass 1 scans all five elements, finds 11 as the minimum, and swaps it with 64: [11, 25, 12, 22, 64]. Four comparisons, one swap.
2. Pass 2 scans positions 2–5, finds 12, and swaps it with 25: [11, 12, 25, 22, 64]. Three comparisons, one swap.
3. Pass 3 scans positions 3–5, finds 22, and swaps it with 25: [11, 12, 22, 25, 64]. Two comparisons, one swap.
4. Pass 4 scans positions 4–5, finds 25 already in place, and swaps nothing: [11, 12, 22, 25, 64]. One comparison, no swap.
5. Position 5 is the only one left, so it must hold the maximum. Done — 10 comparisons, 3 swaps.

The case for fewest writes

Ten comparisons for three swaps is the trade in miniature. Run the same array through bubble sort and you will see comparable comparisons but considerably more swaps, because bubble sort moves an element every time it finds a local disorder rather than once when it knows the answer.

That matters in three real situations. Flash memory and EEPROM wear out after a bounded number of write cycles, so minimising writes extends hardware life. Large records — structs of hundreds of bytes rather than integers — make each swap expensive to execute while comparisons stay cheap, because a comparison usually touches only one key field. And write-through caches or persisted arrays turn every write into work far beyond the array itself.

In those situations the correct question is not "which algorithm makes the fewest comparisons" but "which makes the fewest writes", and selection sort's answer of exactly n−1 is unbeatable among the simple sorts. Cycle sort beats it in theory, at the cost of substantially more comparisons and much more complexity.

How the animation above works

Watch a single pass and you will see the pattern immediately: a long run of amber comparisons with the white marker occasionally jumping to a new candidate minimum, then one coral swap, then a mint bar appearing on the left. The sorted region grows from the left edge, one element per pass, which is the visual opposite of bubble sort's growth from the right.

Set the array size to 50 and note the ratio in the counters below. Comparisons will climb into the hundreds while swaps stay below fifty. That gap is not a quirk of this implementation — it is the algorithm's defining property, and it is the only reason to choose it.

Time complexity

The comparison count is fixed by the structure of the loops, not by the data: (n−1) + (n−2) + … + 1 = n(n−1)/2. That is O(n²) in the best, average and worst case alike. A sorted array, a reversed array and a random array all cost exactly the same number of comparisons, which you can verify by switching the arrangement in the controls and watching the comparison counter land on the identical number every time.

This total predictability is unusual and occasionally useful — the running time is a function of n alone, with no data-dependent variance — but it is bought at the price of never being fast. Insertion sort will beat selection sort on nearly-sorted data by an enormous margin, because insertion sort adapts and selection sort cannot.

The swap count is where the picture inverts: O(n), at most n−1 swaps, and often fewer since a pass whose minimum is already in place skips the swap entirely.

Space and stability

Selection sort uses O(1) auxiliary space — a loop counter and a remembered index. It sorts entirely in place.

It is not stable, and the reason is instructive. The swap at the end of each pass moves an element from far away into position, jumping over everything in between. Consider [4a, 4b, 2], where 4a and 4b are equal keys attached to different records. Pass 1 selects 2 as the minimum and swaps it with position 1, producing [2, 4b, 4a] — the two equal elements have been reversed by a swap that had nothing to do with either of them.

A stable variant exists: instead of swapping, shift the block of elements right and insert the minimum. But that turns O(n) writes into O(n²) writes, which discards the only reason to use selection sort in the first place. If you need stability, use insertion sort.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Selection Sort in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * Selection sort. Performs at most n-1 swaps, which is the fewest of any
 * common comparison sort — the reason to choose it when writes are costly.
 */
function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    // Scan the unsorted suffix without moving anything.
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) minIndex = j;
    }

    // One write per pass, and only when it changes something.
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

console.log(selectionSort([64, 25, 12, 22, 11])); // [11, 12, 22, 25, 64]

Advantages and disadvantages

Real-world applications

• Embedded firmware writing to flash or EEPROM, where each write consumes a finite erase cycle and minimising writes extends device life.
• Sorting small arrays of large structs where a swap copies hundreds of bytes but a comparison reads a single key.
• Systems that need a hard, data-independent time bound for a sort — its complete lack of variance is occasionally a feature in real-time contexts.
• Teaching the distinction between comparison count and write count, which is the clearest lesson the algorithm has to offer.
• As a building block for selection-based problems such as finding the k smallest elements, where you run only k passes rather than n−1.

Interview questions

The questions that actually get asked about Selection Sort, with the answers an interviewer is listening for.

1. Q1. Why is selection sort O(n²) even when the input is already sorted?

   Because the inner loop must scan the entire unsorted region to prove it has found the minimum, and nothing about a completed pass tells the algorithm anything about the ordering of what remains. Bubble sort can exit early because a swap-free pass verifies the whole array; selection sort has no equivalent evidence available, so it always performs n(n−1)/2 comparisons.

2. Q2. Selection sort makes fewer swaps than bubble sort. Why is it still not preferred?

   Because writes are rarely the bottleneck in ordinary software. On typical in-memory data, comparisons and cache behaviour dominate, and insertion sort beats selection sort on both while also being stable and adaptive. Selection sort wins only when a write is genuinely far more expensive than a comparison — flash memory, or very large records.

3. Q3. Is selection sort stable? Can it be made stable?

   It is not stable, because the swap moves a distant element into position and jumps over equal elements in between: [4a, 4b, 2] becomes [2, 4b, 4a]. It can be made stable by shifting the intervening block right and inserting rather than swapping, but that raises the write count from O(n) to O(n²) and eliminates the algorithm's only advantage.

4. Q4. How would you use selection sort to find the k smallest elements?

   Run only the first k passes and stop. Each pass places one more element in its final position, so after k passes the first k slots hold the k smallest values in order, at a cost of O(kn). For small k that beats sorting the whole array, though a heap does it in O(n log k) and wins once k grows.

5. Q5. What is the exact number of comparisons selection sort makes on n elements?

   Exactly n(n−1)/2, always. For 100 elements that is 4,950 comparisons whether the array is sorted, reversed or random. The swap count varies between 0 and n−1 depending on how many passes find their minimum already in place.

Common mistakes

• Swapping inside the inner loop whenever a smaller element is found, instead of only recording its index — this turns the O(n) swap count into O(n²) and destroys the algorithm's one advantage.
• Starting the inner loop at i rather than i + 1, which wastes a comparison of an element with itself on every pass.
• Running the outer loop to n - 1 inclusive rather than n - 2, producing a final pass over a single element that can never do anything.
• Forgetting the minIndex !== i guard, so every pass performs a pointless self-swap and the write count rises to exactly n−1 instead of often being lower.
• Assuming selection sort is stable and using it to sort records by a secondary key after a primary sort — the results will be silently wrong.

Optimisation tips

• Track the maximum as well as the minimum in the same pass and place both ends at once (double-ended selection sort). This roughly halves the number of passes, though the comparison count stays Θ(n²).
• Skip the swap when the minimum is already in position — a one-line guard that saves a write on every already-placed element.
• If you only need the k smallest, stop after k passes rather than sorting the whole array.
• For sorting by an expensive-to-compare key, cache the key alongside the index during the scan so the comparison does not recompute it.
• For any general-purpose sorting of more than about twenty elements, use insertion sort or your language's built-in sort instead — selection sort is a specialist tool, not a default.

Summary

Selection sort repeatedly scans the unsorted region for its minimum and swaps that value into the next position. Comparisons are always exactly n(n−1)/2, giving O(n²) in every case with no adaptivity and no early exit. Swaps are at most n−1, which is the fewest of any common comparison sort.

Use it when writes are expensive and comparisons are cheap — flash storage, large records, wear-limited hardware. For everything else insertion sort is better in almost every respect: adaptive, stable, and faster on real data. Run both on a nearly-sorted array in the comparison lab and the difference is immediate.

Frequently asked questions

Related algorithms

• Bubble Sort

  Repeatedly swap adjacent pairs until the largest values have bubbled to the end.

  O(n²)Beginner

• Insertion Sort

  Grow a sorted prefix by sliding each new value back to where it belongs.

  O(n²)Beginner

• Heap Sort

  Build a max-heap, then repeatedly pull the root to the end of the array.

  O(n log n)Advanced