Skip to content

Selection Sort

This page provides a brief introduction to selection sort.

Definition

Selection sort is a simple and intuitive sorting algorithm. Its working principle is to find the \(i\)-th smallest element (i.e., the smallest element in \(A_{i..n}\)) each time, and then swap this element with the element at the \(i\)-th position in the array.

selection sort animate example

Properties

Stability

The stability of selection sort depends on its specific implementation.

If implemented using a linked list, since insertion and deletion at any position in a linked list are \(O(1)\), there is no need to use a swap (exchange two elements) operation: each time the smallest element is selected from the unsorted part (if there are multiple, pick the first one), it is inserted before the first element of the unsorted part, which ensures stability.

If implemented using an array (the common implementation in OI), since insertion and deletion at any position in an array are \(O(n)\), only swap can be used to move elements from the unsorted part to the sorted part. The swap operation makes the array-based implementation of selection sort unstable.

The implementation examples given below are all based on swapping array elements, and therefore are unstable.

Time Complexity

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

Code 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 ith\gets i\\ 6 & \textbf{for }j\gets i+1\textbf{ to }n\\ 7 & \qquad\qquad\textbf{if }A[j]<A[ith]\\ 8 & \qquad\qquad\qquad ith\gets j\\ 9 & \qquad \text{swap }A[i]\text{ and }A[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
// arr code uses 1-based indexing
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;
    }
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用