cf.completefrontend
SORTING · FOUNDATION

Selection sort

Sort a list by finding the smallest remaining item and moving it to the front, one position at a time.

Time O(n²)Space O(1)2 practice problemsStep-through picture

The idea

Selection sort builds the sorted list from the front. First it scans the whole list for the smallest item and swaps it into position 0. Then it scans the rest for the next smallest and swaps it into position 1. It keeps going until every position is filled.

The scan always looks at every remaining item, so selection sort does about the same amount of comparing whether the list starts sorted or not. Its strength is that it makes very few swaps: at most one per position, so at most n - 1 in total.

That makes it useful when moving an item is much more expensive than comparing two items, and it is a clean way to see the idea "pick the best remaining choice, then repeat".

An everyday example

Arranging books by picking the shortest each time

You want to shelve a pile of books from shortest to tallest. You look through the whole pile, pick the shortest book, and put it first on the shelf. Then you look through what is left, pick the shortest of those, and put it next. You never move a book twice: each one goes straight to its final spot.

How the example maps to the code
In the exampleIn the code
The next empty spot on the shelfPosition i
Looking through the rest of the pileThe inner loop over j
The shortest book seen so farminIndex
Putting it on the shelfSwapping items[i] and items[minIndex]

From the slow way to selection sort

  1. Think about the first position of the sorted list. Whatever goes there has to be the smallest item. The obvious way to find it is to look at every item once and remember the smallest. That costs n - 1 comparisons and tells you exactly what belongs at index 0.
  2. Once the smallest item is at index 0, it never has to move again. The rest of the problem is the same problem, one item smaller: find the smallest of items[1..] and put it at index 1. Repeating this fills the list from the front, one final position at a time.
  3. How do you put the smallest item at index i without disturbing anything? Swap it with whatever is at i. The item that was at i lands somewhere in the unsorted part, which is fine, because the unsorted part has no order to protect. So each position costs one scan and at most one swap.
  4. During the scan you don't need to move anything. You only need to remember where the smallest item so far is, in a number minIndex, and swap once after the scan ends. An outer loop over positions i, an inner scan that updates minIndex, and one swap per position: that loop is selection sort.

How it works

  1. For each position i from 0 to the second-to-last index, everything before i is already sorted and final.
  2. Set minIndex = i, assuming the item at i is the smallest remaining one.
  3. Scan j from i + 1 to the end. Whenever items[j] is smaller than items[minIndex], set minIndex = j.
  4. After the scan, swap items[i] with items[minIndex], unless they are the same position.
  5. Move on to the next i. When i reaches the last index, the last item is automatically the largest.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function selectionSort(items) {
  2. for (let i = 0; i < items.length - 1; i++) {
  3. let minIndex = i;
  4. for (let j = i + 1; j < items.length; j++) {
  5. if (items[j] < items[minIndex]) {
  6. minIndex = j;
  7. }
  8. }
  9. if (minIndex !== i) {
  10. [items[i], items[minIndex]] = [items[minIndex], items[i]];
  11. }
  12. }
  13. return items;
  14. }

How fast it is

TimeO(n²)
Extra memoryO(1)

For each of the n positions it scans all remaining items, about n² / 2 comparisons in every case. It sorts in place and makes at most n - 1 swaps.

  • Best caseO(n²)

    Even an already sorted list like [1, 2, 3, 4] is scanned completely at every position: the scan has no way to stop early. It just makes zero swaps.

  • Average caseO(n²)

    A random list costs the same n × (n - 1) / 2 comparisons, with up to n - 1 swaps.

  • Worst caseO(n²)

    Every input costs the same comparisons. A reversed list like [6, 5, 4, 3, 2, 1] makes only 3 swaps, because each swap fixes two positions.

Common mistakes

  • Swapping every time a smaller item is found during the scan, instead of once after it. That turns it into a slow, swap-heavy sort.
  • Starting the inner loop at j = i instead of i + 1. It works but wastes a comparison every step.
  • Expecting it to keep equal items in order. It does not; use insertion sort or merge sort when stability matters.
  • Expecting a speed-up on sorted input. Selection sort always scans everything.

When to use it

Look for these clues in a problem:

  • Moving or writing an item is expensive, and you want as few swaps as possible.
  • The question asks about the order in which the smallest (or largest) items are picked.
  • The list is small and simple code is preferred.

Check yourself

Answer each one in your head first, then open it.

Why doesn't selection sort get faster on a sorted list?

The scan must look at every remaining item to be sure which is smallest. Nothing in the code lets it stop early, so it makes n × (n - 1) / 2 comparisons no matter what.

How many swaps does it make on [5, 4, 3, 2, 1]?

Two. Step 0 swaps 5 and 1, step 1 swaps 4 and 2, and the 3 in the middle is already in place, as are the rest.

Why does the outer loop stop at items.length - 1?

When only one item is left, it is the biggest of all, and it is already in the last position. Scanning a one-item range would change nothing.

What would go wrong if you swapped every time you found a smaller item during the scan?

The list still ends sorted, but you make up to n² / 2 swaps instead of n - 1, losing the one thing selection sort is good at.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule at the top of each outer step is: items[0..i-1] holds the i smallest items of the list, in sorted order, and every item from i onward is at least as big as each of them. At the start, i = 0 and the sorted part is empty, so the rule is true.

The inner scan compares every item from i to the end against the smallest so far, so when it ends, items[minIndex] is the smallest item left. Swapping it into position i makes items[0..i] the i + 1 smallest items, in order, because it is at least as big as everything before it and no bigger than anything after it. The swap only moves the old items[i] inside the unsorted part, so nothing sorted is disturbed.

The outer loop runs exactly n - 1 times and always ends. At that point the rule says the first n - 1 positions hold the n - 1 smallest items in order. The single item left at the end must be the biggest, so the whole list is sorted.

Notice what the rule does not promise: that equal items keep their order. The swap moves items[i] far to the right, possibly past an equal twin, which is why selection sort is not stable.

Going deeper

3 more ideas

Why the front part stays final

After step i, position i holds the smallest of all the items that were left. Every item after it is at least as big. So nothing later can ever need to move in front of it, and the part 0..i is sorted and final. That rule grows by one each step until it covers the whole list.

Why it is not stable

A sort is stable if equal items keep their original order. Selection sort is not. In [4a, 4b, 1] (two 4s, labeled to tell them apart), step 0 swaps 4a with 1, giving [1, 4b, 4a]: the two 4s switched order. A long-distance swap can jump an item over its equal twin.

How long it takes

Step i compares n - 1 - i pairs, so the total is about n² / 2 comparisons: O(n²), even for a sorted list. The swaps are at most n - 1. For distinct values, this is the fewest swaps any method can sort with, because each swap puts one item into its final place.

Work it by hand

Every step in a table, with why

Sort 6 numbers with two equal 3s. The first scan is shown step by step; the later positions show only their result.

items = [6, 3, 8, 3, 1, 9]

Stepijitems[j]minIndexitemsWhat happensWhy
10131[6, 3, 8, 3, 1, 9]3 < 6: new smallestFill position 0. minIndex starts at 0 (the 6), and 3 beats it.
20281[6, 3, 8, 3, 1, 9]8 is not smallerminIndex stays at 1.
30331[6, 3, 8, 3, 1, 9]3 < 3 is falseA tie does not replace the smallest, because the check is strict. The first 3 stays the choice.
40414[6, 3, 8, 3, 1, 9]1 < 3: new smallest1 is the smallest so far, at index 4.
50594[6, 3, 8, 3, 1, 9]9 is not smallerThe scan ends after 5 comparisons.
60--4[1, 3, 8, 3, 6, 9]Swap items[0] and items[4]1 takes position 0 for good. The 6 lands at index 4, in the unsorted part.
712 to 58, 3, 6, 91[1, 3, 8, 3, 6, 9]minIndex === i: no swapNo item in items[2..5] is smaller than 3 (the other 3 ties), so position 1 is already right.
823 to 53, 6, 93[1, 3, 3, 8, 6, 9]Swap 8 and 3The second 3 is the smallest left. One swap puts it at index 2.
934 to 56, 94[1, 3, 3, 6, 8, 9]Swap 8 and 66 is the smallest of 8, 6, 9.
104594[1, 3, 3, 6, 8, 9]No swap; loop ends9 is not smaller than 8. The outer loop stops at items.length - 1, because the last item is automatically the biggest.

It returns [1, 3, 3, 6, 8, 9] after 15 comparisons (5 + 4 + 3 + 2 + 1) and 3 swaps. The comparison count would be the same 15 for any order of these 6 numbers.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Selection sortO(n²)O(1)Writes are expensive (each one costs far more than a comparison) and the list is small. It makes at most n - 1 swaps.
Insertion sortO(n²)O(1)The list is small or nearly sorted, or you need stability. It can finish in O(n) on sorted input.
Heap sortO(n log n)O(1)You need guaranteed O(n log n) with no extra memory. It is selection sort with a heap to find the best item fast.

Extra memory: O(1): three numbers, i, j, and minIndex, and swaps inside the array.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Selection sort and the other approaches, on a scale where each line up is 10 times more steps.
  • Selection sort, Insertion sort O(n²)
  • Heap sort O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Selection sort1001 million1 trillion
Insertion sort1001 million1 trillion
Heap sort339,96620 million

Inputs that need care

5 tricky inputs
An empty list [] or one item [4]
i < items.length - 1 is false at once (0 < -1 or 0 < 0), so the list comes back untouched.
Already sorted: [2, 4, 6, 8]
Every scan confirms minIndex === i, so the if skips every swap. It still makes all 6 comparisons.
Equal items with labels: [4a, 4b, 1]
Step 0 swaps 4a with 1, giving [1, 4b, 4a]. The two 4s changed order. If you need stability, use insertion sort or merge sort.
Many equal values: [2, 2, 2, 1]
The strict < keeps the first of equal smallest items, so it makes 1 swap. With <= it picks the last of equal items instead, and makes 3 swaps, two of them between equal 2s.
Items where moving is expensive, like large records
This is where selection sort helps: at most n - 1 swaps. You can also sort an array of indexes instead and move the records once at the end.

Variations and follow-ups

Twists interviewers add

Heap sort

The slow part of selection sort is the scan that finds the smallest remaining item, O(n) each time. Heap sort keeps the remaining items in a heap, which hands out the biggest in O(log n). It is the same "pick the best remaining, then repeat" idea, made fast.

Double selection sort

Find both the smallest and the biggest item in one scan, and place them at both ends. It halves the number of outer steps, but the total comparisons stay about the same, so it is still O(n²).

Stable selection sort

Instead of swapping the smallest item into place, take it out and shift the items between i and minIndex one step right, like insertion sort does. Equal items then keep their order, but you lose the small swap count.

Partial selection: the k smallest

Stop the outer loop after k steps. The first k positions hold the k smallest items in order, for O(n × k) work. For small k this is simple and fine; for large k, use a heap or quickselect.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it when a question says "minimum number of swaps" or "each write is expensive". For distinct values, selection sort makes the fewest swaps possible: n minus the number of cycles, where a cycle is a group of items that must rotate among each other's positions.
  • Explain it with the rule: "the front part holds the i smallest items, sorted, and never changes again". Then say the scan is what makes it O(n²) in every case.
  • Test by hand with a list that has equal items, like [2, 1, 2], to show you know it isn't stable, and with a sorted list, to show it gets no speed-up.
  • The common follow-up is "how would you make it faster?". The answer is heap sort: keep the unsorted part in a heap so finding the next item costs O(log n) instead of O(n).

Where frontend code uses it

The same idea in real UI code
  • When each move is costly, such as reordering real DOM nodes, which can trigger layout work, selection sort's at most n - 1 moves can beat sorts that shuffle items around more.
  • Picking the next item to show, such as the most urgent toast notification, by scanning a short list for the best one is a single step of selection sort.
  • "Top 3" widgets over a handful of items often just run three selection steps instead of sorting everything.

Related algorithms