AIOJ

This page will briefly introduce selection sort.

Definition

Selection sort (English: Selection sort) is a simple and intuitive sorting algorithm. Its working principle is to find the $i$ -th smallest element each time (that is, the smallest element in $A_{i..n}$ ), and then swap this element with the element at position $i$ 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 both $O(1)$ , there is no need to use a swap (swapping two elements) operation: each time, after selecting the minimum element from the unsorted part (if there are multiple, select the first one), insert it before the first element of the unsorted part, thereby ensuring stability.

If implemented using an array (the usual implementation in OI), since insertion and deletion at any position in an array are both $O(n)$ , the only option is to use swap to move elements from the unsorted part to the sorted part. The swap operation makes array-based selection sort unstable.

All implementations given below are based on swapping array elements, and are therefore 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 & \qquad \textbf{for }j\gets i+1\textbf{ to }n\\ 7 & \qquad\qquad\textbf{if }A[j] 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]); } } ``` **Python** ```python 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] ``` **Java** ```java // Array arr 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; } } ```