Topics › Sorting › Sorting-I

Selection Sort

Easy TUF ID 947 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array arr of n integers. Sort it in non-decreasing order using the selection sort algorithm. The array should be sorted in place; the order of equal elements does not matter for correctness, although we will look at a variant that preserves it.

Constraints: 1 ≤ n ≤ 10^3, values fit in a 32-bit signed integer. Duplicates and negative numbers are allowed.

Example 1

arr = [13, 46, 24, 52, 20, 9]
answer = [9, 13, 20, 24, 46, 52]      // every element is <= the one after it

Example 2

arr = [5, 4, 4, 1, 1]
answer = [1, 1, 4, 4, 5]              // duplicates stay, nothing is dropped

Approach 1: Select into a new array

Intuition. The idea behind selection sort is one sentence long: the smallest remaining element must come next. The most literal implementation keeps an output array and a “used” flag per input element. Repeatedly scan the input for the smallest element that has not been used yet, append it to the output, and mark it. After n rounds the output holds every element in sorted order.

This is wasteful (we need O(n) extra memory and we re-scan elements we already placed), but it shows the core invariant with nothing else in the way: after k rounds, the output contains the k smallest elements, in order.

Algorithm.

1. Create used[0..n-1], all false, and an output array out of size n.
2. For k from 0 to n - 1:
   • Scan all indices i; among the unused ones keep the index of the smallest value.
   • Mark it used and write its value to out[k].
3. Copy out back into arr.

static void selectionSortExtraSpace(int[] arr) {
    int n = arr.length;
    boolean[] used = new boolean[n];
    int[] out = new int[n];
    for (int k = 0; k < n; k++) {
        int minIdx = -1;
        for (int i = 0; i < n; i++) {
            if (!used[i] && (minIdx == -1 || arr[i] < arr[minIdx])) minIdx = i;
        }
        used[minIdx] = true;
        out[k] = arr[minIdx];
    }
    System.arraycopy(out, 0, arr, 0, n);
}

Complexity. Time O(n^2): n rounds, each scanning all n positions. Space O(n) for used and out.

The minIdx == -1 check is what lets the first unused element become the initial candidate without a separate “find first unused” loop. Because k < n, at least one element is still unused in every round, so minIdx is never -1 when we index with it.

Approach 2: In-place selection sort

Intuition. We do not need a second array. Once we know the smallest element of the unsorted part, we can swap it into position i, the first unsorted slot. The element that used to sit at i is unsorted anyway, so moving it to the vacated position loses nothing. The array therefore splits into a sorted prefix arr[0..i-1] that is already in its final place and an unsorted suffix arr[i..n-1], and each round grows the prefix by one.

The “used” flags disappear because the boundary i plays their role: everything left of i is done, everything from i onwards is a candidate.

Algorithm.

1. For i from 0 to n - 2:
2. Set minIdx = i; for j from i + 1 to n - 1, if arr[j] < arr[minIdx] set minIdx = j.
3. If minIdx != i, swap arr[i] and arr[minIdx].
4. Stop after i = n - 2; the last element is the maximum by elimination.

static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        if (minIdx != i) {
            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }
}

Dry run on arr = [13, 46, 24, 52, 20, 9]:

Five rounds for six elements; the remaining 52 is the maximum and is already where it belongs.

Complexity. Time O(n^2): round i makes n - 1 - i comparisons, so in total n(n-1)/2, regardless of the input. There is no best case, because finding the minimum always requires looking at every candidate. Space O(1): three integer variables.

What selection sort does have going for it is the number of writes: at most n - 1 swaps, i.e. O(n) element moves. Bubble sort and insertion sort can perform O(n^2) moves on a reversed array. When writing is far more expensive than reading (flash memory, a remote store) this property matters.

Approach 3: Stable selection sort

Intuition. A sort is stable when elements with equal keys keep their original relative order. Approach 2 is not stable. Take [2a, 2b, 1] where a and b tag two equal keys: in round 0 the minimum 1 is swapped with 2a, giving [1, 2b, 2a]. The swap jumped 2a over 2b.

The fix is to stop swapping. Instead, lift the minimum out, shift every element between i and minIdx - 1 one step to the right, and drop the minimum into arr[i]. Shifting preserves the order of everything that moves, and because the strict < picks the leftmost minimum, equal keys are consumed in their original order. On [2a, 2b, 1] the shift gives [1, 2a, 2b].

Algorithm.

1. For i from 0 to n - 2, find minIdx exactly as before.
2. Save min = arr[minIdx].
3. For k from minIdx down to i + 1: arr[k] = arr[k - 1].
4. Set arr[i] = min.

static void selectionSortStable(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        int min = arr[minIdx];
        for (int k = minIdx; k > i; k--) arr[k] = arr[k - 1];
        arr[i] = min;
    }
}

Complexity. Time O(n^2): the same comparisons plus up to n - 1 - i moves per round, still quadratic. Space O(1). The price of stability is that we lose the O(n) write bound; the shifting can perform O(n^2) moves on a reversed input.

When sorting plain int values, stability is invisible: two equal integers are indistinguishable. It only matters when the key is part of a bigger record (sort people by age and expect ties to stay in the order they were entered). The int version is still the right place to learn the mechanics.

Edge cases and pitfalls

• Empty or single-element array. n - 1 is -1 or 0, so the outer loop body never runs. Nothing to do, nothing crashes.
• Loop bound i < n - 1, not i < n. Running i to n - 1 is harmless (the inner loop is empty and minIdx == i), but it is one wasted iteration and signals that you have not thought about why the last element is already placed.
• Compare with <, never with subtraction. arr[j] - arr[minIdx] < 0 overflows when the values are near Integer.MIN_VALUE and Integer.MAX_VALUE, and the sign flips. The tests include exactly that pair.
• Duplicates. The strict < keeps the first occurrence of the minimum. Using <= would still sort correctly but would pick the last occurrence, which breaks the stable variant.
• Swapping an element with itself. minIdx == i happens whenever arr[i] is already the minimum. The swap would be a no-op; the if skips it so that the swap count really is bounded by the number of misplaced elements.
• No early exit exists. Unlike bubble sort, you cannot detect “already sorted” during a round without extra comparisons, so selection sort is Θ(n^2) even on sorted input.
• In-place vs. copy. The methods sort the array they are given. If you need the original later, pass arr.clone().

Related problems

• Bubble Sort is the other elementary quadratic sort; it moves the maximum to the end instead of the minimum to the front.
• Insertion Sorting grows a sorted prefix too, but inserts the next element instead of selecting the smallest one, which makes it adaptive.
• Merge Sorting and Quick Sorting are the O(n log n) sorts to move on to once the quadratic ones are clear.