Selection Sort

Selection sort takes a different philosophy from bubble sort. Instead of repeatedly swapping adjacent elements, it identifies the correct element for each position and places it there in a single swap. The algorithm is dead-simple to implement, performs the minimum number of swaps among O(n²) sorts, and serves as an excellent model for understanding loop invariants and selection-based reasoning.

The Algorithm

Selection sort divides the array into two regions: a sorted prefix (initially empty) and an unsorted suffix (initially the entire array). In each iteration:

Scan the unsorted region to find the minimum element.
Swap that minimum with the first element of the unsorted region.
Advance the boundary — the sorted prefix grows by one.

Repeat until the unsorted region is empty.

Core invariant: After iteration i, the first i elements contain the i smallest elements of the array, each in its final sorted position.

This invariant is stronger than bubble sort’s. Bubble sort guarantees the last elements are in place; selection sort guarantees the first elements are in place — and they are the globally correct elements, not elements that happened to bubble to the end.

Java 25 Implementation

void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap minimum into position
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

The if (minIndex != i) guard avoids unnecessary swaps when the minimum element is already in the correct position. This is a micro-optimization — it doesn’t change the asymptotic complexity, but it eliminates wasted writes.

Visual Walkthrough

Sorting [29, 10, 14, 37, 13]:

Iteration 1 (i = 0): Find minimum in [29, 10, 14, 37, 13] → 10 at index 1. Swap arr[0] and arr[1].

[10 | 29, 14, 37, 13]   sorted: [10]

Iteration 2 (i = 1): Find minimum in [29, 14, 37, 13] → 13 at index 4. Swap arr[1] and arr[4].

[10, 13 | 14, 37, 29]   sorted: [10, 13]

Iteration 3 (i = 2): Find minimum in [14, 37, 29] → 14 at index 2. Already in place — no swap.

[10, 13, 14 | 37, 29]   sorted: [10, 13, 14]

Iteration 4 (i = 3): Find minimum in [37, 29] → 29 at index 4. Swap arr[3] and arr[4].

[10, 13, 14, 29 | 37]   sorted: [10, 13, 14, 29]

Result: [10, 13, 14, 29, 37] — sorted.

Notice: only 3 swaps for an array of 5 elements. Compare this with bubble sort’s walkthrough, which required far more swaps for the same-sized input.

Complexity Analysis

Time Complexity

Selection sort’s complexity is always O(n²), regardless of input order. This is its defining characteristic — and its greatest weakness.

Why? The algorithm always scans the entire unsorted region to find the minimum. Iteration 1 scans n - 1 elements, iteration 2 scans n - 2, and so on:

$$(n-1) + (n-2) + \ldots + 1 = \frac{n(n-1)}{2} = O(n^2)$$

It doesn’t matter if the array is already sorted, reverse sorted, or random. Selection sort performs the exact same number of comparisons every time. There is no “best case” advantage — selection sort is not adaptive.

This contrasts sharply with bubble sort (O(n) best case with early termination) and insertion sort (O(n) on sorted input). Selection sort ignores any existing order in the data.

Space Complexity

O(1) — Selection sort is in-place. It uses only a constant number of variables: minIndex, temp, and loop counters.

The Minimum-Swap Property

Selection sort performs at most n - 1 swaps — one per iteration of the outer loop. This makes it the O(n²) sort with the fewest swaps.

Compare swap counts across O(n²) algorithms on an array of n elements in the worst case:

Algorithm	Worst-Case Swaps
Bubble Sort	O(n²) — one swap per inversion
Insertion Sort	O(n²) — one shift per displaced element
Selection Sort	O(n) — exactly n - 1 swaps maximum

This property matters when swap operations are expensive. Consider sorting records on flash memory or EEPROM, where each write degrades the storage medium. Or sorting large objects where swapping involves copying megabytes of data. In these scenarios, selection sort’s O(n) swaps outperform bubble sort’s O(n²) swaps despite both having O(n²) comparisons.

Stability

Selection sort is NOT stable. Swapping the minimum element with the first unsorted element can change the relative order of equal elements.

Example: Sort [(A, 2), (B, 1), (C, 2)] by the numeric key.

Find minimum: (B, 1) at index 1. Swap with index 0.
Result: [(B, 1), (A, 2), (C, 2)]

Now (A, 2) appears before (C, 2) — which matches the original order. But consider [(A, 2), (B, 2), (C, 1)]:

Find minimum: (C, 1) at index 2. Swap with (A, 2) at index 0.
Result: [(C, 1), (B, 2), (A, 2)]

Original order of equal keys (A, 2) and (B, 2) was A before B. After sorting, the order is B before A. Stability violated.

The root cause: long-range swaps. When you swap element at position 0 with element at position 5, you jump over all elements in between, disrupting their relative ordering.

You can make selection sort stable by using insertion instead of swapping (shift all elements right and insert the minimum), but this changes the algorithm into something closer to insertion sort and adds O(n) work per iteration.

Summary

Metric	Value
Best time	O(n²)
Average time	O(n²)
Worst time	O(n²)
Space	O(1)
Stable	No
Adaptive	No
Max swaps	n - 1

Selection Sort vs Bubble Sort

Property	Bubble Sort	Selection Sort
Best case	O(n) with early termination	O(n²) always
Adaptive	Yes	No
Stable	Yes	No
Swaps (worst)	O(n²)	O(n)
Comparisons (worst)	O(n²)	O(n²)
Practical use	Nearly sorted small arrays	Minimizing writes

The trade-off is clear: bubble sort adapts to sorted input and preserves stability, while selection sort minimizes data movement. Choose based on what matters in your context.

The Double Selection Sort Variant

A common optimization scans for both the minimum and maximum in each pass, placing the minimum at the front and the maximum at the end. This halves the number of iterations (but not the total comparisons) and can improve cache performance on large arrays.

void doubleSelectionSort(int[] arr) {
    int n = arr.length;
    for (int left = 0, right = n - 1; left < right; left++, right--) {
        int minIndex = left;
        int maxIndex = left;
        for (int j = left + 1; j <= right; j++) {
            if (arr[j] < arr[minIndex]) minIndex = j;
            if (arr[j] > arr[maxIndex]) maxIndex = j;
        }
        // Place minimum at left boundary
        int temp = arr[left];
        arr[left] = arr[minIndex];
        arr[minIndex] = temp;

        // Adjust maxIndex if it was pointing to left (now swapped)
        if (maxIndex == left) maxIndex = minIndex;

        // Place maximum at right boundary
        temp = arr[right];
        arr[right] = arr[maxIndex];
        arr[maxIndex] = temp;
    }
}

Watch the edge case: if maxIndex == left, the first swap moved the maximum to minIndex. The adjustment maxIndex = minIndex corrects this. Missing this condition is a common bug — and a common interview trap.

When Selection Sort Wins

Write-limited hardware: Flash memory, EEPROM, or network-attached storage where writes are orders of magnitude more expensive than reads.
Small constant-factor needs: For arrays under ~10 elements, the overhead of O(n log n) algorithms (recursion, partitioning, heap operations) exceeds selection sort’s quadratic cost.
Pedagogical clarity: Its loop invariant — “the first i elements are the i smallest in sorted order” — is the clearest of any sorting algorithm. Use it to demonstrate invariant reasoning in interviews.

Interviewer Tips

Know selection sort’s unique selling point: the O(n) swap count. When an interviewer asks “When would you prefer selection sort?”, the answer involves expensive writes.

Explain why it’s not stable: Walk through the equal-key counterexample. Showing a concrete example beats a vague claim — interviewers want to see you reason about edge cases.

Contrast it with insertion sort: Both build a sorted region, but insertion sort grows from the left by inserting into the sorted prefix, while selection sort grows from the left by selecting from the unsorted suffix. Insertion sort is adaptive and stable; selection sort is neither. This comparison question appears in algorithm courses and interviews alike.

Don’t confuse the invariant: Selection sort guarantees the first i elements are globally correct. Insertion sort guarantees the first i elements are sorted relative to each other but not necessarily in their final positions (if more elements remain). This distinction reveals deep understanding.