Selection Sort

Category: Classical
Difficulty: Beginner
Time Complexity: O(n²)
Space Complexity: O(1)

Overview

Selection Sort divides the array into a sorted region at the front and an unsorted region behind it. On each pass it scans the entire unsorted region to find its minimum, then swaps that minimum into the first unsorted slot. It always performs exactly n(n-1)/2 comparisons regardless of the input, and uses at most n-1 swaps — the fewest writes of any simple sort. It is simple and in-place, but not stable and not adaptive, so it is mainly of educational value.

Try It

• Web: Open in Eigenvue →
• Python:

  import eigenvue
  eigenvue.show("selection-sort")

Default Inputs

{
  "array": [
    64,
    25,
    12,
    22,
    11
  ]
}

Input Examples

Default

{
  "array": [
    64,
    25,
    12,
    22,
    11
  ]
}

Already sorted

{
  "array": [
    1,
    2,
    3,
    4,
    5
  ]
}

Reverse sorted

{
  "array": [
    5,
    4,
    3,
    2,
    1
  ]
}

With duplicates

{
  "array": [
    4,
    2,
    4,
    1,
    2
  ]
}

Single element

{
  "array": [
    7
  ]
}

Code

Pseudocode

function selectionSort(array):
  for i = 0 to length(array) - 2:
    minIndex = i
    for j = i + 1 to length(array) - 1:
      if array[j] < array[minIndex]:
        minIndex = j
    swap(array[i], array[minIndex])
  return array

Python

def selection_sort(array: list[int]) -> list[int]:
    n = len(array)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if array[j] < array[min_index]:
                min_index = j
        array[i], array[min_index] = array[min_index], array[i]
    return array

JavaScript

function selectionSort(array) {
  const n = array.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }
    }
    [array[i], array[minIndex]] = [array[minIndex], array[i]];
  }
  return array;
}

Key Concepts

Select the Minimum

Each pass finds the smallest element of the unsorted region and places it at the front. After pass i, the first i+1 elements are in their final sorted positions.

Comparisons vs. Swaps

Selection Sort always makes the same number of comparisons — n(n-1)/2 — but only up to n-1 swaps. When writing to memory is expensive, its low swap count is an advantage over Bubble Sort.

Not Stable, Not Adaptive

Swapping a far-away minimum into place can reorder equal elements, so Selection Sort is not stable. It also does the same work on sorted and unsorted input, so it is not adaptive.

Common Pitfalls

• Assuming it is faster on sorted input: Unlike Insertion Sort, Selection Sort scans the whole unsorted region every pass, so an already-sorted array still costs O(n²) comparisons.
• Expecting stability: Selection Sort is not stable. If stability matters (e.g. sorting records by one field), use Insertion Sort or Merge Sort instead.

Quiz

Q1: How many swaps does Selection Sort perform in the worst case?

• A) O(1)
• B) O(n)
• C) O(n log n)
• D) O(n²)

Show answer

Answer: B) O(n)

Selection Sort performs at most one swap per pass and there are n-1 passes, so at most n-1 = O(n) swaps.

Q2: Is Selection Sort stable?

• A) Yes
• B) No
• C) Only for sorted input
• D) Only for distinct values

Show answer

Answer: B) No

Swapping a distant minimum into the front can move an equal element past its equals, breaking stability.

Q3: How many comparisons does Selection Sort make on an already-sorted array of n elements?

• A) 0
• B) n - 1
• C) n(n-1)/2
• D) n log n

Show answer

Answer: C) n(n-1)/2

It always scans the entire unsorted region, making n(n-1)/2 comparisons regardless of the initial order.

Further Reading

• Selection Sort — Wikipedia (reference)

Related Algorithms

• Bubble Sort
• Insertion Sort
• Heap Sort