Sorting Algorithm

Selection Sort

“The Perfectionist”

Time: O(n²)

Space: O(1)

History

Selection Sort comes from an era where writing to memory was expensive. Imagine carving stone tablets rather than writing to RAM.

It takes a "measure twice, cut once" approach. Instead of swapping constantly like Bubble Sort, Selection Sort scans the entire remaining list to find the absolute smallest item, and only then does it make a move. It is the most predictable of all sorting algorithms.

How It Works

Selection Sort divides the world into two parts: the sorted kingdom (left) and the unsorted wildlands (right). It repeatedly conquers the wildlands one element at a time.

The Algorithm Step-by-Step

Search: Look through the entire unsorted portion of the list.
Identify: Find the index of the absolute minimum value.
Swap: Exchange that minimum value with the first element of the unsorted portion.
Advance: Move the boundary of the sorted kingdom one step to the right.
Repeat: Until the wildlands are empty.

Visual Intuition

Imagine organizing a hand of cards. You look at all the cards, find the Ace, and put it at the front. Then you look at the remaining cards, find the 2, and put it next. That is Selection Sort.

Best CaseO(n²)

It has zero chill. Even if the list is already sorted, it will still scan every element to make sure.

Worst CaseO(n²)

The number of comparisons is always the same: $(n^2 - n) / 2$.

Average CaseO(n²)

It doesn't care about the data order. It does the same work every time.

SpaceO(1)

It's an in-place sort. Low memory footprint.

Code Walkthrough

Real implementations in multiple programming languages. Select a language to view idiomatic code.

1def selection_sort(arr: list[int]) -> None:
2    """Sort array in-place using selection sort."""
3    n = len(arr)
4
5    for i in range(n - 1):
6        # Find minimum element in unsorted portion
7        min_idx = i
8
9        for j in range(i + 1, n):
10            if arr[j] < arr[min_idx]:
11                min_idx = j
12
13        # Swap minimum with first unsorted element
14        if min_idx != i:
15            arr[i], arr[min_idx] = arr[min_idx], arr[i]

Python • .py

Real World Use Cases

1Systems where writing to memory is costly (Flash memory / EEPROM)
2Simple embedded systems
3Situations where you need consistent execution time (no spikes)
4Small lists where code size matters more than speed

Key Insights

It minimizes swaps (maximum $n$ swaps).
It is usually NOT stable (might reorder equal items).
It is completely non-adaptive (doesn't care if list is sorted).
It is robust but slow.

When to Use

Use it when write operations are expensive (like on cheap flash storage) or when you need the sorting time to be perfectly predictable regardless of the input.