Selection Sort Explained: Animated Line-by-Line Guide

Section 01

The Story That Makes Selection Sort Obvious

📖 Real World Analogy

🎱 The Tryout Line-Up

You are a coach lining players up by height, shortest to tallest. You scan the entire squad, spot the single shortest player, and pull them to the front of the line. Then you scan everyone who is left, find the next shortest, and place them second. You repeat, each time scanning the remaining crowd for its minimum and locking it into the next open slot.

Notice the rhythm: a long look across everyone unsorted, then one quick move. You never shuffle people around repeatedly — each chosen player is placed exactly once and never touched again.

That is Selection Sort: repeatedly select the smallest remaining element and swap it into its final position.

Selection Sort splits the array into a sorted part (on the left, already in final position) and an unsorted part (on the right). On each pass it scans the whole unsorted part to find the minimum, then swaps that minimum into the first unsorted slot. The boundary between sorted and unsorted moves one step right every pass.

🧠

The Core Insight

Selection Sort trades comparisons for moves. It does a lot of looking (always about n²/2 comparisons, no matter the input) but only a tiny number of swaps — at most n−1. When writing/moving data is far more expensive than comparing it, that trade can be exactly what you want.

Section 02

The Algorithm in Four Plain-English Steps

🎱 ONE PASS OF SELECTION SORT

Step 1

Assume the first unsorted element is the smallest. Remember its index as min_idx.

Step 2

Scan every remaining element. Whenever you find one smaller than the current minimum, update min_idx to point at it.

Step 3

After the full scan, min_idx holds the smallest of the unsorted part.

Step 4

Swap that minimum into the first unsorted slot. It is now in its final position. Move the boundary right and repeat.

🔍 THE SCAN, LOOPING — FIND THE SMALLEST, THEN LOCK IT IN

The pointer sweeps across the whole unsorted region. The smallest value it finds (here 1) turns amber as the chosen minimum, then locks into the front slot as sorted-green.

Section 03

Hands-On: Watch Every Line of Code Execute

This is the heart of the tutorial. Press Play (or step through manually) and watch the highlighted line of Python on the right move in lock-step with the animated array on the left. The status bar narrates exactly what the active line is doing right now. Notice how the inner if line lights up constantly (all that comparing) while the swap line fires only once per pass. Use Shuffle for a fresh array.

⚡ LIVE TRACE — THIS LINE IS DOING THIS TASK

0 min 🔍 Smallest so far — the value min_idx currently points at.

1def selection_sort(arr):

2 for i in range(len(arr) - 1):

3 min_idx = i

4 for j in range(i + 1, len(arr)):

5 if arr[j] < arr[min_idx]:

6 min_idx = j

7 arr[i], arr[min_idx] = arr[min_idx], arr[i]

8 return arr

Press Play or Step ▶ to begin.

Speed Step 0 / 0

🔑

How to Read the Animation

The dashed amber slot is i — the destination for this pass. The solid amber bar is the smallest found so far; watch it hop whenever min_idx = j fires. The blue bar is the current comparison. When arr[i], arr[min_idx] = … lights up, the winner swaps into slot i and turns sorted-green — permanently.

Section 04

The Full Python Implementation

Here is the same algorithm as a clean, copy-ready function, plus a tiny driver that prints the array before and after sorting.

def selection_sort(arr):
    # The sorted region grows from the left, one element per pass.
    for i in range(len(arr) - 1):
        min_idx = i                 # assume the first unsorted item is smallest

        # Scan the unsorted part for a smaller element.
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j         # found a new minimum

        # One swap puts the minimum in its final place.
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr


# --- driver ---
data = [5, 3, 8, 1, 9, 2, 7]
print("Before:", data)
selection_sort(data)
print("After: ", data)

OUTPUT

Before: [5, 3, 8, 1, 9, 2, 7] After: [1, 2, 3, 5, 7, 8, 9]

A Verbose Version That Narrates Each Pass

Run this once to see the sorted region grow and to count how few swaps actually happen.

def selection_sort_verbose(arr):
    swaps = 0
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
            swaps += 1
        print(f"Pass {i}: min={arr[i]:>2}  ->  {arr}")
    print(f"Total swaps: {swaps}")
    return arr

selection_sort_verbose([5, 3, 8, 1, 9, 2, 7])

OUTPUT

Pass 0: min= 1 -> [1, 3, 8, 5, 9, 2, 7] Pass 1: min= 2 -> [1, 2, 8, 5, 9, 3, 7] Pass 2: min= 3 -> [1, 2, 3, 5, 9, 8, 7] Pass 3: min= 5 -> [1, 2, 3, 5, 9, 8, 7] Pass 4: min= 7 -> [1, 2, 3, 5, 7, 8, 9] Pass 5: min= 8 -> [1, 2, 3, 5, 7, 8, 9] Total swaps: 4

✅

Only 4 Swaps for 7 Elements

Two passes (3 and 5) needed no swap at all because the minimum was already in place. Selection Sort never performs more than n−1 swaps total — that is its defining strength.

Section 05

Why Use Selection Sort? The Real Benefits

🧩

Dead Simple to Reason About

~8 lines, no recursion

A pair of plain loops and a swap. There is no edge-case bookkeeping, no extra memory, and the behaviour is identical on every input — which makes it predictable and a popular first sorting algorithm to learn.

🔄

Minimum Number of Swaps

≤ n − 1 writes

This is the headline benefit. It performs at most n−1 swaps — O(n) writes total — versus O(n²) for Bubble Sort. When a single write is costly, this matters enormously.

📐

In-Place, Constant Memory

O(1) extra space

It sorts inside the original array using only a couple of loop counters and an index. No auxiliary arrays, no recursion stack — ideal for tightly memory-constrained environments.

💾

Where "Few Writes" Really Pays Off

On hardware like flash memory and EEPROM, every write physically wears out the medium, so minimising writes extends device life. The same logic applies when each element is a huge record that is expensive to move but cheap to compare by key — Selection Sort moves each item at most once.

Section 06

When to Use It — and When Not To

✅

Writes Are Expensive

Flash/EEPROM wear, or moving large records where each move is costly but a key comparison is cheap. Fewest possible swaps wins here.

minimise data movement

✅

Small Arrays

For roughly n < 10–20 elements, the quadratic cost is negligible and the simplicity is welcome. Common in interviews and teaching.

n < ~20

✅

Predictable, Uniform Cost

It always does the same work, so its runtime is highly consistent — handy where worst-case timing must equal average-case timing.

deterministic timing

❌

Large Datasets

At O(n²) comparisons in every case, sorting thousands+ of elements is far too slow. Use Merge Sort, Quick Sort, or a built-in sort().

n in the thousands+

❌

Nearly-Sorted Data

It is not adaptive — an already-sorted array costs exactly as much as a random one. Insertion Sort is the better choice here.

use Insertion Sort

❌

Stability Required

The standard swap version is not stable — equal keys can be reordered. If relative order of equal items must hold, pick a stable sort.

equal-key order matters

Section 07

Time & Space Complexity

Case	When It Happens	Comparisons	Swaps	Time
Best	Already sorted	~n²/2 (full scan anyway)	0–(n−1)	O(n²)
Average	Random order	~n²/2	≤ n−1	O(n²)
Worst	Any order	~n²/2	≤ n−1	O(n²)
Space	Any input (in-place)	—	—	O(1) auxiliary

⚠️

Same Cost No Matter What

The two nested loops always run their full course: the outer loop n−1 times, the inner loop scanning the entire shrinking unsorted region. There is no early exit, so best, average, and worst case are all O(n²). Selection Sort cannot get faster on friendly data — it simply is not adaptive.

Section 08

Comparisons vs Swaps, Side by Side

For an array of n = 5, the scan work is fixed, but the swap work depends only on whether each minimum was already home.

🔍 Comparisons (always the same)

Pass i	Elements scanned	Comparisons
0	4	4
1	3	3
2	2	2
3	1	1
Total	—	10 = n(n−1)/2

🔄 Swaps (at most n − 1)

Pass i	Min already at i?	Swaps
0	No	1
1	Yes	0
2	No	1
3	No	1
Total	—	≤ 4 = n−1

Section 09

How One Pass Flows

Assume a Minimum

min_idx = i — treat the first unsorted element as the smallest until proven otherwise.

Scan the Rest

for j in range(i + 1, len(arr)) — walk through every remaining element exactly once.

Track the Smallest

if arr[j] < arr[min_idx]: min_idx = j — remember the index of any new, smaller value you meet.

Swap Into Place

arr[i], arr[min_idx] = arr[min_idx], arr[i] — one swap locks the minimum into its final slot. The sorted region just grew by one.

Section 10

Selection Sort vs Its Cousins

Property	Selection Sort	Bubble Sort	Insertion Sort	Merge Sort
Best case	O(n²)	O(n)	O(n)	O(n log n)
Average / worst	O(n²)	O(n²)	O(n²)	O(n log n)
Swaps / writes	O(n) — fewest	O(n²)	O(n²) shifts	O(n log n)
Extra space	O(1)	O(1)	O(1)	O(n)
Stable?	No (by default)	Yes	Yes	Yes
Adaptive?	No	Somewhat	Yes — strongly	No
Best for…	Costly writes, small data	Teaching only	Small / nearly-sorted	Large general data

🏆

The Practitioner's Take

Reach for Selection Sort in the narrow but real case where moving data is the bottleneck — it guarantees the fewest writes of any common sort. For almost everything else, Insertion Sort beats it on small/nearly-sorted inputs (it is adaptive and stable), and an O(n log n) sort wins on anything large.

Section 11

Golden Rules

🎱 Selection Sort — Things Worth Memorising

The sorted region is always on the left and each placed element is in its final position — it is never touched again. That invariant is the whole algorithm.

Comparisons are fixed at ~n²/2 regardless of input; swaps are at most n−1. Selection Sort trades lots of looking for very little moving.

Track the index (min_idx), not the value. Swapping by index lets you place the minimum with a single exchange after the scan finishes.

Guard the swap with if min_idx != i: when you want to skip no-op swaps — a tiny optimisation that avoids pointless writes (and keeps the swap count truly minimal).

It is not adaptive. Do not expect a speed-up on sorted data — if your data is often nearly sorted, use Insertion Sort instead.

The default version is not stable. If you need stability, shift elements instead of swapping (which sacrifices the few-writes advantage) or choose a stable sort.