Selection Sort

Tags

Selection Sort

Category

Sorting

Difficulty

Easy

Problem Statement

Implement the selection sort algorithm to sort an array of integers in ascending order. Selection sort works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning of the unsorted portion.

Intuition

Divide the array into a sorted prefix and an unsorted suffix. In each iteration, scan the unsorted suffix for the smallest element, then swap it into the first position of the unsorted suffix. The sorted prefix grows by one element each time.

Approach

  1. For each index i from 0 to length - 2:
    • Assume i is the index of the minimum element.
    • Scan from i + 1 to the end to find the actual minimum.
    • Swap the minimum element with the element at index i.
  2. Return the sorted array.

Pseudocode

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

Time & Space Complexity

  • Time: O(n^2) in all cases (best, average, worst). The algorithm always scans the full unsorted portion regardless of the initial order.
  • Space: O(1) — Sorting is done in-place with only a constant number of variables.

Key Insights

  • Selection sort performs exactly n-1 swaps in all cases, making it optimal in terms of swap count. This is useful when writes are expensive.
  • Unlike bubble sort and insertion sort, selection sort has no best-case improvement — it always performs O(n^2) comparisons.
  • Selection sort is not stable in its standard form (swapping can change the relative order of equal elements).
  • It is simple to implement and easy to reason about correctness.

Edge Cases

  • Empty array — nothing to sort.
  • Single-element array — already sorted.
  • Already sorted array — still performs O(n^2) comparisons but no meaningful swaps.
  • Array with all identical elements — n-1 no-op swaps are performed.
  • Array with two elements — one comparison and at most one swap.

Linked mentions