Selection Sort

Easy10–15 min

Topics

SortingArray

Companies

AmazonMicrosoft

Given an array of integers, sort it in non-decreasing order using **Selection Sort** — repeatedly find the smallest value among what's left to place, and put it into its correct position. Unlike bubble sort or insertion sort, selection sort makes at most one swap per pass — it spends its time searching for the minimum rather than moving values around during the search. That makes the number of writes to the array very predictable (exactly n-1 swaps total), even though the number of comparisons is the same O(n²) as the other simple sorts.

Test Case 1:

Input:arr = [7, 2, 9, 4, 2, 8]

Output:[2, 2, 4, 7, 8, 9]

Explanation:A typical unsorted array with a repeated value.

Test Case 2:

Input:arr = []

Output:[]

Explanation:An empty array is already sorted.

Test Case 3:

Input:arr = [5]

Output:[5]

Explanation:A single element is already sorted.

Constraints

◆0 ≤ arr.length ≤ 200
◆-1000 ≤ arr[i] ≤ 1000
◆Sort in non-decreasing order

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Collect Minimums into a New Array

Good

For each output position, scan every value that hasn't been used yet, find the smallest one, and record it. Repeat until every value has been placed. This never touches the original array — it builds the sorted result in a brand-new array (with an auxiliary "used" marker per element), which costs O(n) extra memory that the in-place version doesn't need.

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public int[] selectionSort(int[] arr) {
        int n = arr.length;
        boolean[] used = new boolean[n];
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int minIdx = -1;
            for (int j = 0; j < n; j++) {
                if (!used[j] && (minIdx == -1 || arr[j] < arr[minIdx])) {
                    minIdx = j;
                }
            }
            result[i] = arr[minIdx];
            used[minIdx] = true;
        }
        return result;
    }
}

Optimal — In-Place, Swap Into Position

Optimal

Grow a sorted prefix from the left. For each position i, scan the rest of the array to find the index of the smallest remaining value, then swap it directly into position i. No second array is ever allocated — every value stays inside the original array the whole time, just getting swapped into its final resting spot one position at a time.