Skip to content

Volume ITechnology

4.0.25 — Selection Sort ​

Classic · Easy · the sort with the fewest swaps

The problem ​

Sort a list in increasing order without sort().

[64, 25, 12, 22, 11]  →  [11, 12, 22, 25, 64]

The idea ​

This is how most people sort a hand of cards laid out on a table. Find the smallest card. Put it first. From the cards left, find the smallest. Put it second. Keep going.

In a list, the left part grows into the sorted answer. The right part holds what is left. Each round selects the smallest value in the right part and swaps it to the front of the right part. That position now joins the sorted part. The sorted part grows by one each round.

The solution ​

python
def selection_sort(nums: list[int]) -> None:
    n = len(nums)
    for i in range(n - 1):                 # (1)
        smallest = i                       # (2)
        for j in range(i + 1, n):          # (3)
            if nums[j] < nums[smallest]:
                smallest = j
        if smallest != i:                  # (4)
            nums[i], nums[smallest] = nums[smallest], nums[i]

a = [64, 25, 12, 22, 11]
selection_sort(a)
print(a)   # → [11, 12, 22, 25, 64]

(1) Position i is the next spot to fill. Everything before i is already sorted and final. We stop at n - 2, because once all other values are placed, the last one is in place too.

(2) Remember the position of the smallest value, not the value itself. We need the position to swap it later.

(3) Search the unsorted part, from i + 1 to the end, for anything smaller.

(4) Swap the smallest into position i. If it is already there, skip the swap. That avoids the self-swap problem from 4.0.1 if someone later rewrites the swap in a trickier way.

Trace ​

On [64, 25, 12, 22, 11]:

ismallest in nums[i:]swaplist after
011 (pos 4)64 ↔ 1111 25 12 22 64
112 (pos 2)25 ↔ 1211 12 25 22 64
222 (pos 3)25 ↔ 2211 12 22 25 64
325 (pos 3)none11 12 22 25 64

Complexity, worked out ​

Comparisons. Round 0 compares n - 1 values, round 1 compares n - 2, and so on.

(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}

That is O(n^2), and here is the important part: it is O(n^2) every time, even on a sorted list. The search in each round must look at every remaining value to be sure it has found the smallest. Nothing tells it to stop early. Selection sort has no best case. That is its biggest weakness.

Swaps. At most one per round, so at most n - 1 swaps in total. That is O(n) swaps, far fewer than bubble sort's up to \frac{n(n-1)}{2}. This is selection sort's one real strength.

When does the swap count matter? When writing is much more expensive than reading. Flash memory, like in a USB stick or an SSD, wears out a little with every write. Each memory cell survives only a limited number of writes. A sort that writes each element at most once or twice wears the memory less.

Memory. O(1) extra. It is in place.

CaseTime
BestO(n^2)
AverageO(n^2)
WorstO(n^2)
Swapsat most n - 1
Extra memoryO(1)
StableNo

Why it is not stable ​

The long-distance swap can jump a value over an equal one. Take three cards, written as value and suit: [4♠, 4♥, 2♦].

  • Round 0: the smallest is 2♦ at position 2. Swap it with position 0. The list becomes [2♦, 4♥, 4♠].

The two 4s have changed order. 4♠ was first, and now it is last. That broken order is what "not stable" means.

python
cards = [(4, "spade"), (4, "heart"), (2, "diamond")]

def selection_sort_by_value(items):
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j][0] < items[smallest][0]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]

selection_sort_by_value(cards)
print(cards)   # → [(2, 'diamond'), (4, 'heart'), (4, 'spade')]

It can be made stable. Instead of swapping, take the smallest value out and shift everything between i and its old position one step right to make room. That keeps equal values in order. But shifting costs up to O(n) writes per round, which throws away the one advantage selection sort had.

Selection sort's real descendant ​

The weak spot is the search. Finding the smallest remaining value takes O(n) each round. If a data structure could hand you the smallest value in O(\log n), the whole sort would drop to O(n \log n). That structure exists. It is called a heap, and selection sort with a heap is heap sort, in 4.0.29.

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"What is the best case of selection sort?" Still O(n^2). Each round must look at every remaining value to be sure it found the smallest. It can never stop early, even on a sorted list.

"How is it different from bubble sort?" Both make about n^2/2 comparisons. Selection sort makes at most n - 1 swaps. Bubble sort can make many more swaps, but it is stable and can finish early on sorted input.

"Is selection sort stable?" No. The long swap can jump a value over an equal one. The three-card example on this page shows it.

"When would you use it?" When writing to memory is much more costly than reading, and the list is small.

One thing to volunteer: "Selection sort with a heap to find the smallest value is heap sort."

Next: 4.0.26 Insertion Sort. The simple sort that real libraries actually use.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet