What is selection sort (selection sorts)?

AlgorithmsJunior~2 min read

Short answer

Selection sort is a simple comparison-based algorithm: at each step it finds the minimum (or maximum) element of the unsorted part of the array and swaps it with the first element of that part. It works in-place, requires O(1) extra memory, runs in O(n²) in the best/average/worst cases, and is usually unstable. Pros: simplicity and a minimal number of swaps; cons: slow on large data.

Detailed breakdown

Algorithm idea

Split the array into two parts: the left one already sorted, the right one still unsorted.
Find the index of the minimum element in the right (unsorted) part.
Swap that minimum with the first element of the unsorted part.
Move the boundary of the sorted part one step to the right and repeat until the end.

Complexity and properties

Time: O(n²) in the worst, average, and best cases (always performs ~n(n-1)/2 comparisons).
Memory: O(1) (in-place).
Number of swaps: O(n) (the minimum among the simple quadratic sorts).
Stability: usually unstable (equal elements can swap places). A stable version is possible by shifting elements instead of swapping.
Adaptivity: not adaptive - even for nearly sorted arrays it performs the same comparisons.

Pseudocode

text

for i = 0 to n-2:
  min = i
  for j = i+1 to n-1:
    if A[j] < A[min]:
      min = j
  swap A[i], A[min]

JavaScript example (regular, unstable version)

function selectionSort(arr, compare = (a, b) => a - b) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (compare(arr[j], arr[minIdx]) < 0) {
        minIdx = j;
      }
    }
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}

// Example
// console.log(selectionSort([64, 25, 12, 22, 11])); // [11, 12, 22, 25, 64]

Step-by-step example

Array: [64, 25, 12, 22, 11]

text

Step 1: minimum 11 (index 4) → swap with index 0
[11, 25, 12, 22, 64]
Step 2: minimum among [25, 12, 22, 64] = 12 (index 2) → swap with index 1
[11, 12, 25, 22, 64]
Step 3: minimum among [25, 22, 64] = 22 (index 3) → swap with index 2
[11, 12, 22, 25, 64]
Step 4: minimum among [25, 64] = 25 → no swap needed
[11, 12, 22, 25, 64]

Stable version (shifting instead of swapping)

To make selection sort stable, the found minimum is not swapped in place but "inserted" at position i, shifting a block of elements one position to the right. This preserves the relative order of equal elements at the cost of more assignments.

function stableSelectionSort(arr, compare = (a, b) => a - b) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (compare(arr[j], arr[minIdx]) < 0) {
        minIdx = j;
      }
    }
    const key = arr[minIdx];
    while (minIdx > i) {
      arr[minIdx] = arr[minIdx - 1];
      minIdx--;
    }
    arr[i] = key;
  }
  return arr;
}

// Example
// console.log(stableSelectionSort([3, 2, 2, 1])); // [1, 2, 2, 3] - the original order of the equal "2"s is preserved

When it is appropriate to use

Teaching and reviewing the basic principles of sorting.
When a minimal number of swaps/writes is critical (for example, media with expensive write operations).
Very small arrays, where simplicity matters more than speed (although insertion sort is usually better on nearly sorted data).

Common interview questions

Is selection sort stable? Usually not: swapping the minimum into position i can change the order of equal elements. Stability is achieved by shifting instead of swapping.
How does it differ from bubble sort and insertion sort? Bubble sort makes many swaps but can finish early on nearly sorted arrays; selection sort makes few swaps but a fixed number of comparisons (not adaptive). Insertion sort is faster on nearly sorted data but makes more moves; selection sort saves on swaps.
How many comparisons/swaps does it perform? Comparisons ≈ n(n-1)/2; swaps no more than n-1 (exactly one per pass when needed).

Variations

Selecting the maximum and placing it at the end (an equivalent idea, a pass from the right).
Two-directional selection sort: in one pass find both the minimum and the maximum and place them in position (roughly halves the number of passes, but is more complex to implement).
For linked lists: convenient to implement stably by moving nodes instead of swapping values.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.