Selection Sort Complete Guide

Algorithm • easy

Selection sort scans the unsorted portion of the array, finds the smallest value, and swaps it into position. Then it repeats on the rest.

It performs the **minimum** number of swaps of any comparison sort: at most n−1, regardless of input order. That's its one real advantage.

Comparisons stay at O(n²) even when the input is already sorted, so it's almost always slower than insertion sort in practice.

Typical Complexity Baseline

Metric	Value
Time	`O(n^2)`
Space	`O(1)`
Complexity Note 3	Swaps `O(n)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Selection sort find min, swap into place

Each pass scans the unsorted region to find the minimum and swaps it to the front.

Step 1/34Pass 1: start scanning from index 0. min so far = arr[0]=6.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Selection sort in 3 minutes

Channel: Michael Sambol

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Sorted boundary

What it is Index marking where the sorted prefix ends and the unsorted suffix begins.

Why it matters Sorted boundary is a required building block for understanding how Selection Sort stays correct and performant on large inputs.

Minimum scan

What it is Inner loop that finds the index of the smallest value in the unsorted suffix.

Why it matters Minimum scan is a required building block for understanding how Selection Sort stays correct and performant on large inputs.

Swap into place

What it is Single swap that moves the minimum to the sorted boundary.

Why it matters Swap into place is a required building block for understanding how Selection Sort stays correct and performant on large inputs.

Boundary advance

What it is Increment the boundary so the just-placed value is now part of the sorted prefix.

Why it matters Boundary advance is a required building block for understanding how Selection Sort stays correct and performant on large inputs.

In-place

What it is Sorts the input array directly using O(1) extra memory.

Why it matters Sorts the input array directly using O(1) extra memory. In Selection Sort, this definition helps you reason about correctness and complexity when inputs scale.

Unstable

What it is Equal values may end up in a different relative order than the input. Selection sort is unstable by default.

Why it matters Equal values may end up in a different relative order than the input. Selection sort is unstable by default. In Selection Sort, this definition helps you reason about correctness and complexity when inputs scale.

Swap-minimal

What it is At most n−1 swaps total, the lowest of any comparison sort.

Why it matters At most n−1 swaps total, the lowest of any comparison sort. In Selection Sort, this definition helps you reason about correctness and complexity when inputs scale.

Online

What it is Cannot start sorting until all input is available, unlike insertion sort.

Why it matters Cannot start sorting until all input is available, unlike insertion sort. In Selection Sort, this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/34

Pass 1: start scanning from index 0. min so far = arr[0]=6.

Step 2/34

arr[1]=3 < current min → new min = 3 (index 1).

Step 3/34

arr[2]=8 ≥ 3 → min stays at index 1.

Step 4/34

arr[3]=1 < current min → new min = 1 (index 3).

Step 5/34

arr[4]=5 ≥ 1 → min stays at index 3.

Step 6/34

arr[5]=2 ≥ 1 → min stays at index 3.

Step 7/34

arr[6]=7 ≥ 1 → min stays at index 3.

Step 8/34

Swap arr[0] ↔ arr[3]. arr[0]=1 is locked.

Step 9/34

Pass 2: start scanning from index 1. min so far = arr[1]=3.

Step 10/34

arr[2]=8 ≥ 3 → min stays at index 1.

Step 11/34

arr[3]=6 ≥ 3 → min stays at index 1.

Step 12/34

arr[4]=5 ≥ 3 → min stays at index 1.

Step 13/34

arr[5]=2 < current min → new min = 2 (index 5).

Step 14/34

arr[6]=7 ≥ 2 → min stays at index 5.

Step 15/34

Swap arr[1] ↔ arr[5]. arr[1]=2 is locked.

Step 16/34

Pass 3: start scanning from index 2. min so far = arr[2]=8.

Step 17/34

arr[3]=6 < current min → new min = 6 (index 3).

Step 18/34

arr[4]=5 < current min → new min = 5 (index 4).

Step 19/34

arr[5]=3 < current min → new min = 3 (index 5).

Step 20/34

arr[6]=7 ≥ 3 → min stays at index 5.

Step 21/34

Swap arr[2] ↔ arr[5]. arr[2]=3 is locked.

Step 22/34

Pass 4: start scanning from index 3. min so far = arr[3]=6.

Step 23/34

arr[4]=5 < current min → new min = 5 (index 4).

Step 24/34

arr[5]=8 ≥ 5 → min stays at index 4.

Step 25/34

arr[6]=7 ≥ 5 → min stays at index 4.

Step 26/34

Swap arr[3] ↔ arr[4]. arr[3]=5 is locked.

Step 27/34

Pass 5: start scanning from index 4. min so far = arr[4]=6.

Step 28/34

arr[5]=8 ≥ 6 → min stays at index 4.

Step 29/34

arr[6]=7 ≥ 6 → min stays at index 4.

Step 30/34

min was already at index 4 → no swap. arr[4]=6 locked.

Step 31/34

Pass 6: start scanning from index 5. min so far = arr[5]=8.

Step 32/34

arr[6]=7 < current min → new min = 7 (index 6).

Step 33/34

Swap arr[5] ↔ arr[6]. arr[5]=7 is locked.

Step 34/34

Sorted! Always n²/2 comparisons but only n-1 swaps.

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Insertion Sort

Choose this when Choose selection sort when swap cost dominates comparison cost (e.g. moving large objects).

Tradeoff Insertion sort runs O(n) on nearly-sorted input; selection always runs O(n²).

vs. Bubble Sort

Choose this when Selection sort does n−1 swaps total versus bubble's O(n²) swaps. Pick it when swaps are costly.

Tradeoff Both are O(n²) comparisons; bubble sort gets early-exit on sorted input, selection does not.

vs. Heap Sort

Choose this when Selection is simpler and clearer for tiny n.

Tradeoff Heap sort is O(n log n), practically always faster for n > ~50.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Embedded systems

Firmware for low-RAM devices sometimes selects sort small fixed-size buffers because it needs zero extra memory and fewer writes than bubble.

Takeaway Constant memory and minimal writes can matter more than asymptotic time for tiny n.

Selection algorithms

QuickSelect is a randomized cousin of selection sort, used to find the kth smallest in O(n). Production code (e.g. NumPy's partition) builds on this idea.

Takeaway Selection-style scans are the foundation for partial-sort and order-statistic algorithms.

CS classrooms worldwide

Selection sort is often taught right after bubble sort because it isolates the 'find min' subroutine, a building block reused everywhere.

Takeaway Decomposing 'find then place' makes more advanced algorithms easier to understand.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

The outer loop tracks the sorted boundary. The inner loop finds the minimum index in the unsorted suffix. Exactly one swap per outer iteration.

Complexity: Time O(n²), Space O(1), Swaps ≤ n−1

Selection sort with swap-minimal property

Language

function selectionSort(values: number[]): number[] {
  const sortedValues = [...values]
  for (let sortedBoundary = 0; sortedBoundary < sortedValues.length - 1; sortedBoundary += 1) {
    let minimumIndex = sortedBoundary
    for (let scanIndex = sortedBoundary + 1; scanIndex < sortedValues.length; scanIndex += 1) {
      if (sortedValues[scanIndex] < sortedValues[minimumIndex]) {
        minimumIndex = scanIndex
      }
    }
    if (minimumIndex !== sortedBoundary) {
      ;[sortedValues[sortedBoundary], sortedValues[minimumIndex]] = [sortedValues[minimumIndex], sortedValues[sortedBoundary]]
    }
  }
  return sortedValues
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Forgetting to skip the swap when minIndex equals the boundary wastes a no-op swap, but worse: it kills stability if you ever try to make the sort stable.
Re-scanning the sorted prefix in the inner loop the inner loop must start at boundary + 1.
Using selection sort on n > a few thousand. It's almost always the wrong choice at scale.
Assuming it's stable it isn't. The swap can leapfrog an equal value backwards.
Off-by-one in the outer loop it should run to length − 1, not length.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

Start by writing the core invariant in one sentence before coding.
Test empty, single-item, and duplicate-heavy inputs early.
Pick the pattern first (map, pointers, recursion, heap, etc.), then implement details.
Track both time and space complexity while iterating on correctness.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

When write operations are far more expensive than reads (e.g. flash memory wear, expensive object moves).
When you need to find the kth smallest while sorting. Selection sort exposes that intermediate state naturally.
Teaching: it cleanly separates the 'find minimum' subproblem from the 'place it' subproblem.

LeetCode-specific tips (pattern-identification signals)

Identification signal: focus on verbs like optimize, order, schedule, traverse, or shortest path; these often indicate algorithm-first problems.
Identification signal: if brute force is easy to write but constraints are large, you likely need a known algorithmic pattern.
Map the prompt to pattern families first (search, traversal, greedy, DP, graph) before coding details.
For Selection Sort questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Sort an Array	Medium	`O(n²)` for selection approach
2	Sort Colors	Medium	`O(n)` Dutch flag, `O(n²)` selection
3	Kth Largest Element in an Array	Medium	`O(n)` average with QuickSelect
4	Find K Closest Elements	Medium	`O(log n + k)`
5	Top K Frequent Elements	Medium	`O(n log k)`
6	K Closest Points to Origin	Medium	`O(n log k)`
7	Wiggle Sort	Medium	`O(n)`