DSA Sorting

Selection Sort

Flash memory on an embedded logger charges per write. Scanning the unsorted suffix is cheap; rewriting the buffer is not.

Selection sort spends a fixed quadratic number of comparisons so it can commit each next minimum with at most one swap. It is and , but not in the usual swap form, and not adaptive.

Algorithm journey

Final prefix

a[0:i] already holds the i smallest values in final order.

Scan the suffix

Find the minimum index in a[i:n].

One commit write

Swap that minimum into position i.

Grow i

Repeat until one element remains.

What actually happens

Naive idea: keep finding the global minimum with a fresh full scan and rebuilding an output list. Correct, but it copies everything and still does Theta(n^2) comparisons.

Better idea: commit minima in place. You still pay n(n - 1)/2 comparisons, yet array writes drop to O(n).

It still fails when you need stability, adaptivity, or large-n performance. Already sorted input does not help; every suffix is fully scanned.

Invariant

Before pass i, a[0:i] contains the globally smallest i values in sorted final order; the inner scan keeps minIndex as the minimum of a[i:j].

How to choose selection sort

1. Are writes far more expensive than reads? Selection can win on tiny arrays with that cost model.

2. Need stability? Use insertion/merge/TimSort, or a careful stable selection variant with shifts.

3. Large n? Prefer an O(n log n) comparison sort or a domain-specific linear-time sort.

Quantitative check

For any distinct-key input of size n, comparisons are exactly n(n - 1)/2. Swaps are at most n - 1. At n = 10^4 that is about 5 x 10^7 comparisons regardless of order.

The two nested invariants

A correctness argument must explain both the outer boundary and the inner scan. The inner loop proves that the remembered candidate is truly the suffix minimum; the outer loop then commits that minimum to a final position.

Inner scan invariant

Before examining index j, minIndex points to the smallest value in a[i:j]. Comparing a[j] either keeps that fact true or updates the candidate.

Outer pass invariant

Before pass i, a[0:i] contains the globally smallest i values in sorted, final order. Swapping in the suffix minimum extends that prefix by exactly one.

Initialization

At i = 0 the final prefix is empty, so the outer invariant is vacuously true.

Maintenance

The complete suffix scan finds a value no larger than any remaining value; placing it at i makes that position final.

Termination

After n − 1 selections, one value remains. It must be the largest and is already in the last position.

Interactive: candidate scan versus committed write

The violet tile is the minimum seen so far. With duplicate keys, watch the first long-distance swap move 4a behind 4b: a concrete counterexample to stability.

Selection scan laboratory

Scan the whole active suffix, remember its minimum, then commit one swap.

The letters preserve original identity: watch whether 4a stays before 4b.

Pass 0 · start

Step 1 / 25

Comparisons

Array writes

Swaps

What changed

Start with an empty sorted prefix.

Invariant

All values still belong to the unsorted suffix.

active / comparingminimum candidatefinal prefix

Counting convention: one key comparison compares two values; one algorithmic assignment into an array cell is one write. During insertion, clearing the displayed source is only a conceptual gap animation, not an extra assignment. A swap uses two array writes (the temporary local variable is not counted).

Original interactive selection-sort visualizer (retained)

Run, pause, or single-step the original bar animation to watch each suffix minimum enter the sorted prefix.

Speed:

ℹ️ Ready

Comparing/Active

Sorted

Reference implementation

Initialize the candidate to the boundary itself, update it only for a strictly smaller key, and skip the swap when the minimum is already in place. That self-swap guard does not improve comparison time, but it avoids needless writes.

Python

python

def selection_sort(a):
    n = len(a)

    for i in range(n - 1):
        min_index = i

        for j in range(i + 1, n):
            if a[j] < a[min_index]:
                min_index = j

        if min_index != i:            # avoid a self-swap
            a[i], a[min_index] = a[min_index], a[i]

    return a

Java

java

final class SelectionSort {
    static int[] sort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int minIndex = i;

            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[minIndex]) {
                    minIndex = j;
                }
            }

            if (minIndex != i) {
                int temp = a[i];
                a[i] = a[minIndex];
                a[minIndex] = temp;
            }
        }

        return a;
    }
}

Exact operation counts

Comparisons

n(n − 1) / 2

Pass i performs n − i − 1 comparisons. Their sum is fixed, regardless of whether the input is sorted, random, reversed, or all equal.

Swaps

0 … n − 1

With the self-swap guard, some passes write nothing. At most one real swap occurs per pass; input order determines the exact count.

Array writes

≤ 2(n − 1)

Under a two-array-write swap model. This is the feature that distinguishes selection sort from other elementary sorts.

Case	Time	Why	Auxiliary space
Best	Θ(n²)	Sorted input still needs proof that each suffix minimum is at its boundary.	Θ(1)
Average	Θ(n²)	The same triangular set of index pairs is compared.	Θ(1)
Worst	Θ(n²)	The same scans occur; only the number of swaps changes.	Θ(1)

Why the ordinary algorithm is not stable

Stability means equal-key records retain their input order. Consider [4a, 4b, 3, 5, 6]. The first pass swaps 3 with 4a, producing [3, 4b, 4a, 5, 6]. No later pass restores the equal fours, so the final output reverses them even though the scan used a strict comparison.

The source of instability

A non-adjacent swap can move the boundary item past an equal record. Choosing the leftmost or rightmost minimum changes tie behavior but does not make the swap-based algorithm stable in general.

A genuinely stable variant

Find the leftmost minimum, remove it, shift every intervening value one position right, and insert the minimum at i. Order is preserved, but writes can become Θ(n²), surrendering selection sort's main advantage.

Choosing among the elementary sorts

Property	Selection	Bubble	Insertion
Value comparisons	Exactly n(n − 1)/2	n − 1 best; n(n − 1)/2 worst	Depends on inversions; Θ(n) best
Array writes	At most 2(n − 1)	2 per inversion	One per shift + key placement
Stable by default	No	Yes	Yes
Adaptive to order	No	Partly, with early exit	Yes

Selection sort is the natural choice only when comparisons are cheap, writes are unusually expensive, input is small, and stability is not required. Real flash storage adds erase blocks and wear-leveling, so “fewer swaps” alone is not enough to choose a storage algorithm.

Variants and related ideas

Maximum-to-the-right

Scan the active unsorted prefix for its largest value and place it at the right boundary, growing a final suffix. This is symmetric to minimum-to-the-left and has identical costs and stability issues.

Bidirectional selection

Find both minimum and maximum in each pass and place them at both ends. It halves outer passes, not the Θ(n²) comparison class; index updates after the first swap require care.

Partial selection

Stopping after k passes gives the k smallest values in sorted order in Θ(kn) time. If only the kth value is needed, Quickselect is typically better on average.

Heap selection

A heap also repeatedly selects an extreme, but maintains the candidate structure between removals. Heap sort reaches Θ(n log n) time at the cost of less sequential access and instability.

Edge cases and reasoning

Implementation checklist

Run only n − 1 passes; the last position follows automatically.
Start minIndex = i, not zero, so the final prefix is never reconsidered.
Scan from i + 1; comparing the candidate with itself adds no information.
Skip self-swaps, especially when writes are the reason for choosing the algorithm.
For records, swap whole records or indices, not only their sort keys.

Checks that sharpen the proof

Why is the best case still quadratic?
How do you derive the exact triangular comparison count?
Give a concrete counterexample to stability.
How would you make it stable, and which advantage would that sacrifice?
What does the array contain after exactly k passes?

Exercises

Give a four-element array with duplicate keys where one swap destroys input order of equals.
Compare write counts for selection vs bubble on a reverse-sorted array of n = 100.
Is there an input where selection does fewer than n(n - 1)/2 value comparisons in the standard algorithm? Why or why not?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): selection sort as an elementary baseline.
Knuth, The Art of Computer Programming, Vol. 3: minimum-extraction sorting.
Sedgewick & Wayne, Algorithms: elementary sorts comparison (selection vs insertion).

Takeaway

Selection sort makes a deliberate trade: exactly Θ(n²) comparisons for at most Θ(n) swaps. Its invariant is clean and its write bound is useful to reason about, but the ordinary version is neither stable nor adaptive. Use it as a counting and correctness exercise, or in a genuinely write-sensitive tiny problem, not as a general-purpose sort.