Selection Sort

Introduction

Selection Sort works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning. It’s like sorting a hand of cards by scanning for the smallest card each time and moving it to the front.

Selection Sort is simple to understand and implement, but it’s always O(n²) — even on sorted input. It makes the minimum number of swaps (at most n-1), which can matter when writes are expensive. You should know Arrays and Big-O Notation before reading this.

How it works

[29, 10, 14, 37, 13]

Pass 1: Find min (10), swap with index 0
[10, 29, 14, 37, 13]

Pass 2: Find min in [29, 14, 37, 13] → 13, swap with index 1
[10, 13, 14, 37, 29]

Pass 3: Find min in [14, 37, 29] → 14, already at index 2
[10, 13, 14, 37, 29]

Pass 4: Find min in [37, 29] → 29, swap with index 3
[10, 13, 14, 29, 37]

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

Implementation

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;

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

    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

console.log(selectionSort([29, 10, 14, 37, 13]));  // [10, 13, 14, 29, 37]

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_index = i

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

        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

print(selection_sort([29, 10, 14, 37, 13]))  # [10, 13, 14, 29, 37]

public static int[] selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;

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

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

Complexity analysis

Space: O(1) — sorts in place.

Stable: No — the swap can move equal elements past each other. For example, sorting [3a, 2, 3b] produces [2, 3b, 3a].

Swaps: At most n-1 swaps, compared to O(n²) swaps for Bubble Sort.

When to use Selection Sort

• When write/swap cost is high (e.g., writing to flash memory) — Selection Sort minimizes swaps
• When you need to find the k smallest elements — stop after k passes
• As a teaching tool to understand sorting fundamentals

For everything else, Insertion Sort is a better simple sort (adaptive, stable, and faster on nearly-sorted data).

Practice problems

1. Sort an array using Selection Sort
2. Find the k-th smallest element (stop Selection Sort after k passes)
3. Sort an array by frequency of elements