Skip to content

Selection Sort

This page gives a brief introduction to selection sort.

Definition

Selection sort is a simple, intuitive sorting algorithm. In step \(i\) it finds the \(i\)-th smallest element (that is, the smallest element of \(A_{i..n}\)) and swaps it with the element at position \(i\) of the array.

selection sort animate example

Properties

Stability

Whether selection sort is stable depends on the implementation.

On a linked list, inserting and deleting at any position take \(O(1)\), so no swap (exchanging two elements) is needed: each time, pick the smallest element of the unsorted part (the first one if there are several) and insert it before the first element of the unsorted part. This keeps the sort stable.

An array implementation usually calls swap to move the smallest element into the sorted part, which takes fewer moves, and is therefore not stable.

The implementations below all swap array elements, so all of them are unstable.

Time complexity

The best-case, average-case and worst-case time complexity of selection sort are all \(O(n^2)\).

Implementation

Pseudocode

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements.} \\ 2 & \textbf{Output. } A\text{ will be sorted in nondecreasing order.} \\ 3 & \textbf{Method. } \\ 4 & \textbf{for } i\gets 1\textbf{ to }n-1\\ 5 & \qquad \textit{ith}\gets i\\ 6 & \qquad \textbf{for }j\gets i+1\textbf{ to }n\\ 7 & \qquad\qquad\textbf{if }A[j]<A[\textit{ith}]\\ 8 & \qquad\qquad\qquad \textit{ith}\gets j\\ 9 & \qquad \text{swap }A[i]\text{ and }A[\textit{ith}]\\ \end{array} \]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <utility>

void selection_sort(int* a, int n) {
  for (int i = 1; i < n; ++i) {
    int ith = i;
    for (int j = i + 1; j <= n; ++j) {
      if (a[j] < a[ith]) {
        ith = j;
      }
    }
    std::swap(a[i], a[ith]);
  }
}
1
2
3
4
5
6
7
def selection_sort(a, n):
    for i in range(1, n):
        ith = i
        for j in range(i + 1, n + 1):
            if a[j] < a[ith]:
                ith = j
        a[i], a[ith] = a[ith], a[i]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// the array arr is 1-indexed
static void selection_sort(int[] arr, int n) {
    for (int i = 1; i < n; i++) {
        int ith = i;
        for (int j = i + 1; j <= n; j++) {
            if (arr[j] < arr[ith]) {
                ith = j;
            }
        }
        // swap
        int temp = arr[i];
        arr[i] = arr[ith];
        arr[ith] = temp;
    }
}