Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Selection Sort

EASYProblemSolveExternal Links

Description

Given an array arr of integers, sort the array in non-decreasing (ascending) order using the Selection Sort algorithm.

Selection Sort is one of the simplest sorting algorithms. The idea is to divide the array into two parts: a sorted portion on the left and an unsorted portion on the right. In each pass, you find the smallest element in the unsorted portion and move it to the end of the sorted portion by swapping it with the first unsorted element.

You must implement this specific algorithm — not just produce a sorted array by any means.

Examples

Example 1

Input: arr = [4, 1, 3, 9, 7]

Output: [1, 3, 4, 7, 9]

Explanation: Selection Sort proceeds as follows:

  • Pass 1: Find minimum in [4, 1, 3, 9, 7] → 1 at index 1. Swap with index 0. Array: [1, 4, 3, 9, 7]
  • Pass 2: Find minimum in [4, 3, 9, 7] → 3 at index 2. Swap with index 1. Array: [1, 3, 4, 9, 7]
  • Pass 3: Find minimum in [4, 9, 7] → 4 at index 2. Already in place. Array: [1, 3, 4, 9, 7]
  • Pass 4: Find minimum in [9, 7] → 7 at index 4. Swap with index 3. Array: [1, 3, 4, 7, 9]
  • The last element 9 is automatically in the correct position.

Example 2

Input: arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Explanation: This is the worst-case input where the array is in completely reverse order. Selection Sort still performs the same number of comparisons regardless — it always scans the entire unsorted portion each pass. Every pass requires a swap (no element is already in place).

Example 3

Input: arr = [38, 31, 20, 14, 30]

Output: [14, 20, 30, 31, 38]

Explanation:

  • Pass 1: Minimum of [38, 31, 20, 14, 30] is 14 (index 3). Swap with index 0. → [14, 31, 20, 38, 30]
  • Pass 2: Minimum of [31, 20, 38, 30] is 20 (index 2). Swap with index 1. → [14, 20, 31, 38, 30]
  • Pass 3: Minimum of [31, 38, 30] is 30 (index 4). Swap with index 2. → [14, 20, 30, 38, 31]
  • Pass 4: Minimum of [38, 31] is 31 (index 4). Swap with index 3. → [14, 20, 30, 31, 38]

Constraints

  • 1 ≤ arr.length ≤ 10^3
  • 1 ≤ arr[i] ≤ 10^6

Editorial

Brute Force

Intuition

Before learning Selection Sort, let's think about how a complete beginner might sort an array.

The most naive idea: repeatedly scan the entire array to find the global minimum, remove it from the array, and append it to a new result array. After extracting all elements this way, the result array is sorted.

Imagine you have a pile of numbered cards. You spread them out, find the smallest card, take it out and put it in a new pile. Then find the next smallest from the remaining cards, take it out and place it next in the new pile. Repeat until the original pile is empty.

This approach is intuitive and correct, but it uses extra space for the result array and involves shifting elements around when we 'remove' from the middle of the original array.

Step-by-Step Explanation

Let's trace with arr = [4, 1, 3, 9, 7]:

Step 1: Scan entire array [4, 1, 3, 9, 7] for minimum → 1 (at index 1). Copy 1 to result. Mark index 1 as used. Result: [1].

Step 2: Scan array skipping used indices. Remaining: [4, 3, 9, 7]. Minimum → 3 (index 2). Copy to result. Result: [1, 3].

Step 3: Remaining: [4, 9, 7]. Minimum → 4 (index 0). Copy to result. Result: [1, 3, 4].

Step 4: Remaining: [9, 7]. Minimum → 7 (index 4). Copy to result. Result: [1, 3, 4, 7].

Step 5: Remaining: [9]. Only one left → 9. Copy to result. Result: [1, 3, 4, 7, 9].

This works but uses O(n) extra space for the result array and a boolean array to track which elements are used.

Algorithm

  1. Create an empty result array and a boolean array used of size n (all false)
  2. Repeat n times:
    a. Scan the original array for the minimum element among unused elements
    b. Append this minimum to result
    c. Mark it as used
  3. Copy result back to the original array

Code

#include <vector>
#include <climits>
using namespace std;

void selectionSortBrute(vector<int>& arr) {
    int n = arr.size();
    vector<int> result;
    vector<bool> used(n, false);
    
    for (int i = 0; i < n; i++) {
        int minVal = INT_MAX;
        int minIdx = -1;
        for (int j = 0; j < n; j++) {
            if (!used[j] && arr[j] < minVal) {
                minVal = arr[j];
                minIdx = j;
            }
        }
        result.push_back(minVal);
        used[minIdx] = true;
    }
    
    arr = result;
}
def selection_sort_brute(arr):
    n = len(arr)
    result = []
    used = [False] * n
    
    for i in range(n):
        min_val = float('inf')
        min_idx = -1
        for j in range(n):
            if not used[j] and arr[j] < min_val:
                min_val = arr[j]
                min_idx = j
        result.append(min_val)
        used[min_idx] = True
    
    arr[:] = result
class Solution {
    void selectionSortBrute(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        boolean[] used = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            int minVal = Integer.MAX_VALUE;
            int minIdx = -1;
            for (int j = 0; j < n; j++) {
                if (!used[j] && arr[j] < minVal) {
                    minVal = arr[j];
                    minIdx = j;
                }
            }
            result[i] = minVal;
            used[minIdx] = true;
        }
        
        System.arraycopy(result, 0, arr, 0, n);
    }
}

Complexity Analysis

Time Complexity: O(n²)

We scan the array n times. In the first pass, we check all n elements; in the second, we still check all n (skipping used ones via a flag check, but the loop still runs n times). Total comparisons: n + n + ... + n = n × n = O(n²).

Space Complexity: O(n)

We use two extra arrays: result of size n and used of size n, giving O(n) extra space. This is wasteful — can we sort without extra arrays?

Why This Approach Is Not Efficient

The brute force approach uses O(n) extra space for the result array and the boolean tracking array. For a sorting algorithm, this is unnecessary overhead.

The key insight: instead of copying the minimum element to a separate result array, we can swap it with the first unsorted element. This places the minimum directly into its correct position in the original array — no extra array needed.

By maintaining a boundary between the sorted portion (left) and unsorted portion (right), each pass simply finds the minimum in the unsorted portion and swaps it into place. The sorted portion grows by one element per pass, and the unsorted portion shrinks by one.

This in-place optimization eliminates the need for any extra data structures, reducing space complexity from O(n) to O(1) while keeping the same O(n²) time complexity.

Optimal Approach - Selection Sort (In-Place)

Intuition

Selection Sort divides the array into two regions:

  1. Sorted region (left side): Elements that are already in their final sorted positions
  2. Unsorted region (right side): Elements that still need to be sorted

Initially, the sorted region is empty and the unsorted region is the entire array.

In each pass, we scan the unsorted region to find the minimum element, then swap it with the first element of the unsorted region. This extends the sorted region by one and shrinks the unsorted region by one.

Think of it like organizing books on a shelf. You look at all the unsorted books, find the one with the smallest number, and swap it to the leftmost open spot on the sorted side. Then you find the next smallest among the remaining unsorted books, and swap it to the next spot. Repeat until all books are sorted.

After n-1 passes, the entire array is sorted. (The last element automatically falls into the correct position once all others are placed.)

The beauty of this approach is that it sorts in-place — no extra arrays needed. Each pass does exactly one swap (or zero swaps if the minimum is already at the correct position), making it memory-write-efficient compared to algorithms like Bubble Sort.

Step-by-Step Explanation

Let's trace Selection Sort on arr = [4, 1, 3, 9, 7]:

Pass 1 (i = 0): Find minimum in unsorted region [4, 1, 3, 9, 7] (indices 0-4).

  • Compare: min_idx = 0 (val 4). Check index 1: 1 < 4 → min_idx = 1. Check index 2: 3 > 1 → no change. Check index 3: 9 > 1 → no change. Check index 4: 7 > 1 → no change.
  • Minimum is 1 at index 1. Swap arr[0] and arr[1].
  • Array: [1, 4, 3, 9, 7]. Sorted region: [1].

Pass 2 (i = 1): Find minimum in unsorted region [4, 3, 9, 7] (indices 1-4).

  • Compare: min_idx = 1 (val 4). Check index 2: 3 < 4 → min_idx = 2. Check index 3: 9 > 3 → no change. Check index 4: 7 > 3 → no change.
  • Minimum is 3 at index 2. Swap arr[1] and arr[2].
  • Array: [1, 3, 4, 9, 7]. Sorted region: [1, 3].

Pass 3 (i = 2): Find minimum in unsorted region [4, 9, 7] (indices 2-4).

  • Compare: min_idx = 2 (val 4). Check index 3: 9 > 4 → no change. Check index 4: 7 > 4 → no change.
  • Minimum is 4 at index 2. It's already in position — no swap needed.
  • Array: [1, 3, 4, 9, 7]. Sorted region: [1, 3, 4].

Pass 4 (i = 3): Find minimum in unsorted region [9, 7] (indices 3-4).

  • Compare: min_idx = 3 (val 9). Check index 4: 7 < 9 → min_idx = 4.
  • Minimum is 7 at index 4. Swap arr[3] and arr[4].
  • Array: [1, 3, 4, 7, 9]. Sorted region: [1, 3, 4, 7, 9].

Result: [1, 3, 4, 7, 9]

Selection Sort — Find Minimum, Swap Into Place — Watch how Selection Sort builds the sorted region one element at a time. In each pass, the minimum of the unsorted region is found and swapped into its correct position.

Algorithm

  1. For i from 0 to n-2 (each pass places one element):
    a. Set min_idx = i (assume the first unsorted element is the minimum)
    b. For j from i+1 to n-1 (scan the unsorted region):
    • If arr[j] < arr[min_idx], update min_idx = j
      c. If min_idx ≠ i, swap arr[i] and arr[min_idx]
  2. The array is now sorted

Code

#include <vector>
#include <algorithm>
using namespace std;

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    
    for (int i = 0; i < n - 1; i++) {
        // Find the minimum element in the unsorted region
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        
        // Swap minimum element with the first unsorted element
        if (min_idx != i) {
            swap(arr[i], arr[min_idx]);
        }
    }
}
def selection_sort(arr):
    n = len(arr)
    
    for i in range(n - 1):
        # Find the minimum element in the unsorted region
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Swap minimum element with the first unsorted element
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
class Solution {
    void selectionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in the unsorted region
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            
            // Swap minimum element with the first unsorted element
            if (minIdx != i) {
                int temp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = temp;
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n²) — in ALL cases (best, average, worst)

The outer loop runs n-1 times. In pass i, the inner loop scans n - i - 1 elements. Total comparisons:

(n-1) + (n-2) + (n-3) + ... + 2 + 1 = n(n-1)/2 = O(n²)

Unlike Bubble Sort (which can short-circuit if no swaps occur), Selection Sort always performs the same number of comparisons regardless of whether the array is already sorted, reverse sorted, or random. There is no best-case optimization.

Space Complexity: O(1)

Selection Sort is an in-place algorithm. It only uses a constant amount of extra memory — the variables i, j, min_idx, and a temporary variable for swapping. No extra arrays or data structures are needed.

Number of Swaps: At most n-1

Each pass performs at most one swap. This is a significant advantage over Bubble Sort (which may perform O(n²) swaps). When memory writes are expensive (e.g., writing to flash memory), Selection Sort's minimal swap count is valuable.

Stability: Selection Sort is NOT stable — it can change the relative order of equal elements. For example, [5a, 3, 5b, 2] → after the first pass, 2 swaps with 5a, giving [2, 3, 5b, 5a], reversing the relative order of the two 5s.