☕ Buy me a coffee — $3

Selection Sort

Overview

Selection Sort is a simple comparison-based sorting algorithm that divides the input list into two parts: a sorted sublist and an unsorted sublist. The algorithm repeatedly finds the minimum (or maximum) element from the unsorted sublist and moves it to the beginning of the sorted sublist.

The algorithm maintains two subarrays: one that is already sorted (initially empty) and one that is unsorted. In each iteration, it selects the smallest element from the unsorted subarray and swaps it with the leftmost element of the unsorted subarray.

Selection sort has a defining feature that separates it from every other elementary sort: it performs the minimum possible number of swaps. Sorting n elements takes exactly n−1 swaps in the worst case, you cannot do fewer with a comparison-based algorithm. That property mattered enormously on early hardware where writing to memory was slow or costly, and it still matters today in specialised settings like flash storage, where every write wears the physical cells. Whether you should ever actually use selection sort in 2026 is a different question, addressed below, but its swap-minimising guarantee is the reason it survives in the literature.

History

Selection sort predates almost every other sorting algorithm in the computing literature because it is the algorithm you invent by accident when you try to explain sorting to someone who has never seen it before. Ask a person how they would sort a set of index cards from smallest to largest number, and they will almost always describe a variant of selection sort: scan for the smallest, put it first, scan the rest for the smallest, put it second, and so on. This makes it a natural starting point for teaching sorting, and it appears in the earliest computing textbooks, often before bubble sort, for that reason.

In the early literature it is sometimes called straight selection sort or simply selection sort, distinguished from its more elaborate cousin heap sort which Robert W. Floyd and J.W.J. Williams turned into an O(n log n) algorithm in 1964 by making the "find the minimum" step logarithmic rather than linear. In that sense heapsort is not a different family of algorithm from selection sort but rather selection sort with a smarter data structure, you can teach heapsort by starting with selection sort and asking "how do we speed up the inner loop?"

The classic theoretical result about selection sort was proved implicitly by these swap-count arguments: no comparison-based sort can achieve fewer than n−1 swaps on the worst-case input, because at least n−1 elements must move from their starting position for the array to become sorted. Selection sort's guaranteed n−1 swaps therefore places it on the theoretical minimum in that specific dimension, a fact that led to a small but persistent line of research into "write-optimal" sorting for storage systems where reads are much cheaper than writes.

How It Works

The algorithm works by:

  1. Finding the minimum element in the unsorted portion of the array
  2. Swapping it with the first element of the unsorted portion
  3. Moving the boundary between sorted and unsorted portions one position to the right
  4. Repeating until the entire array is sorted

Algorithm


SelectionSort(arr):
    n = length of arr
    for i = 0 to n - 1:
        min_index = i
        for j = i + 1 to n - 1:
            if arr[j] < arr[min_index]:
                min_index = j
        swap arr[i] and arr[min_index]

Implementation


def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Find minimum element in remaining unsorted array
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # Swap the found minimum element with the first element
        arr[i], arr[min_index] = arr[min_index], arr[i]
    
    return arr

Complexity Analysis

  • Time Complexity:
    • Best Case: O(n²) - still needs to check all elements
    • Average Case: O(n²)
    • Worst Case: O(n²) - always performs n(n-1)/2 comparisons
  • Space Complexity: O(1) - only uses a constant amount of extra space

Selection Sort always performs O(n²) comparisons regardless of input order, making it inefficient for large datasets. However, it minimizes the number of swaps (only n swaps in worst case).

Characteristics

  • Stable: No - may change relative order of equal elements
  • In-place: Yes - only requires O(1) extra space
  • Adaptive: No - always performs the same number of comparisons
  • Online: No - requires the entire array to be present

Why Selection Sort Is Not Stable

Stability, the property that equal elements preserve their relative input order, matters more often than beginners expect, because real-world sorts are usually keyed on one field of a compound record. A stable sort by "last name" applied to a list that was previously sorted by "first name" gives you correctly-ordered names; an unstable sort scrambles the within-last-name ordering, and you lose the previous sort as a side effect. This is why Python's list.sort(), Java's Collections.sort() and SQL's ORDER BY are all stable by contract.

Selection sort is not stable, and the reason is worth understanding because it is a surprisingly subtle consequence of the algorithm's structure. When selection sort finds the minimum in the unsorted suffix and swaps it with the first element of that suffix, the swap can jump an equal element over a copy of itself. Concretely, consider sorting [4a, 5, 3, 4b, 1] where 4a and 4b are two records with the same key but different identity. The first pass finds 1 as the minimum and swaps it with position 0: [1, 5, 3, 4b, 4a]. The 4a and 4b have now been reordered by the swap, and no further step will fix that. This is why selection sort scrambles duplicate-heavy inputs and is unsuitable for multi-key sorting.

You can convert selection sort into a stable algorithm by replacing the swap with a "shift and insert", move all elements between the minimum's position and the target slot one step to the right, then place the minimum. This preserves relative order of equals but costs O(n) per pass instead of O(1), turning the whole algorithm's move count from O(n) into O(n²), erasing the swap-minimality that was selection sort's one theoretical advantage. The version you almost always see is the unstable swap-based one, and if you need stability you should reach for insertion sort or mergesort instead.

Variants and Cousins

Bidirectional Selection Sort

On each pass, find both the minimum and the maximum of the remaining unsorted region in a single scan, and place them at the two ends. This halves the number of passes at the cost of a slightly more complex inner loop, and it can be useful when the constant factor matters and stability does not.

Bingo Sort

A tuned version of selection sort for arrays with many duplicates. Instead of finding the minimum once per pass, bingo sort finds the minimum, then in the same pass moves every copy of that value to the sorted region before returning to find the next distinct minimum. For an array with k distinct values, bingo sort runs in O(kn), which is a substantial speedup when k is much smaller than n, sorting a million-element array of Boolean flags takes two passes, not a million.

Heap Sort as Optimised Selection Sort

The most consequential variant is heap sort, which uses a binary heap to make the "find the maximum" step O(log n) instead of O(n). The overall structure is still selection sort's outer loop, take the extremum, place it at the current end, but the total complexity drops from O(n²) to O(n log n) while remaining in-place. If you understand selection sort, you understand almost half of heap sort already; the rest is the heapify machinery.

Pancake Sorting

A theoretical variant restricted to a single operation: reverse any prefix of the array. The natural algorithm is selection-sort-shaped, find the largest remaining element, flip it to the top with one prefix reversal, then flip it to its final position with a second. Pancake sorting takes at most 2n reversals and has a small but active research literature around the exact minimum number of flips needed for the worst case.

Common Misconceptions

  • "Selection sort is faster than bubble sort." The comparison count is the same, both perform exactly n(n−1)/2 comparisons in the worst case. Selection sort performs O(n) swaps versus bubble sort's O(n²), which matters when writes are expensive. But bubble sort with the early-termination check can run in O(n) on already-sorted input; selection sort cannot, because its outer loop always runs n−1 times and its inner scan cannot exit early, it has no way to know whether it has already found the true minimum until it has looked at every remaining element. On random data the two algorithms are roughly comparable; on nearly-sorted data, bubble sort wins.
  • "Selection sort has a good best case." No, the best, average and worst cases are all Θ(n²) comparisons. It is one of the very few sorting algorithms whose running time is independent of the input distribution, which makes its performance perfectly predictable at the cost of never being fast.
  • "You can make it adaptive by exiting early when nothing changes." Not without changing the algorithm fundamentally. Bubble sort can detect a sorted array with a single pass because a pass that performs no swaps proves sortedness by contradiction. Selection sort has no such shortcut, each pass finds a minimum whether or not the array is sorted, and finding the minimum requires looking at every remaining element.

When to Use Selection Sort

Selection sort is a textbook algorithm more than a working programmer's tool, but there is a narrower set of real cases where it earns its keep:

  • When writes are dramatically more expensive than comparisons. Flash memory wears out after a bounded number of writes per cell; erasing an EEPROM sector to change a single byte can take milliseconds. Selection sort's guarantee of at most n−1 writes to the destination array is genuinely useful in these settings, even a modern algorithm like introsort makes O(n log n) writes.
  • When you need to select and place, not just sort. "Find the k smallest elements" runs in O(kn) with selection sort's outer loop stopped after k iterations. For small k this beats sorting the whole array and taking a slice, though a partial heapsort or quickselect is usually better.
  • For teaching the elementary sorts. Selection sort's structure, maintain a growing sorted prefix, extend it one element at a time, is the mental model behind heap sort, and is easier to explain than bubble sort's less-obvious invariants. Many instructors introduce it first for exactly this reason.
  • For very small arrays where its predictability is worth having. On arrays of 5–10 elements the constant-factor differences between the elementary sorts matter less than clarity and correctness, and selection sort has the simplest loop invariant to reason about.

Outside these niches, prefer insertion sort for its speed on small and nearly-sorted arrays, heap sort for the same guarantees at O(n log n) instead of O(n²), or a hybrid sort like Timsort for general-purpose work.

Example

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

Initial: [64, 25, 12, 22, 11]
Pass 1:  [11, 25, 12, 22, 64]  (11 is minimum, swap with 64)
Pass 2:  [11, 12, 25, 22, 64]  (12 is minimum, swap with 25)
Pass 3:  [11, 12, 22, 25, 64]  (22 is minimum, swap with 25)
Pass 4:  [11, 12, 22, 25, 64]  (25 is already in place)
Sorted:  [11, 12, 22, 25, 64]

Related Algorithms

Explore other sorting algorithms: