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.
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
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
1 2 3 4 5 6 7 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
This page is an unofficial English translation of the original OI Wiki page (revision b469442a), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: partychicken, 24OI-bot, ouuan, NachtgeistW, Early0v0, Xeonacid, Enter-tainer, Junyan721113, iamtwz, mcendu, ksyx, ZbohZbp, Menci, shawlleyw, WException, TrickEye, Tiphereth-A, tfia, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.