11.2 Selection sort¶
Selection sort works very simply: in each round, select the smallest element from the unsorted section and place it at the end of the sorted section.
For an array of length \(n\), the algorithm proceeds as shown below.
- Initially, all elements are unsorted, so the unsorted index interval is \([0, n-1]\).
- Select the smallest element in \([0, n-1]\) and swap it with the element at index \(0\). The first element is now sorted.
- Select the smallest element in \([1, n-1]\) and swap it with the element at index \(1\). The first two elements are now sorted.
- Continue in this way. After \(n - 1\) rounds of selection and swapping, the first \(n - 1\) elements are sorted.
- The remaining element must be the largest and needs no sorting. The array is now sorted.











Figure 11-2 Steps of selection sort
In the code, \(k\) tracks the smallest element in the unsorted section:
selection_sort.py
def selection_sort(nums: list[int]):
"""Selection sort"""
n = len(nums)
# Outer loop: the unsorted range is [i, n-1]
for i in range(n - 1):
# Inner loop: find the smallest element in the unsorted range
k = i
for j in range(i + 1, n):
if nums[j] < nums[k]:
k = j # Record the index of the smallest element
# Swap the smallest element with the first element of the unsorted range
nums[i], nums[k] = nums[k], nums[i]
selection_sort.cpp
/* Selection sort */
void selectionSort(vector<int> &nums) {
int n = nums.size();
// Outer loop: the unsorted range is [i, n-1]
for (int i = 0; i < n - 1; i++) {
// Inner loop: find the smallest element in the unsorted range
int k = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[k])
k = j; // Record the index of the smallest element
}
// Swap the smallest element with the first element of the unsorted range
swap(nums[i], nums[k]);
}
}
selection_sort.java
/* Selection sort */
void selectionSort(int[] nums) {
int n = nums.length;
// Outer loop: the unsorted range is [i, n-1]
for (int i = 0; i < n - 1; i++) {
// Inner loop: find the smallest element in the unsorted range
int k = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[k])
k = j; // Record the index of the smallest element
}
// Swap the smallest element with the first element of the unsorted range
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
}
}
selection_sort.cs
/* Selection sort */
void SelectionSort(int[] nums) {
int n = nums.Length;
// Outer loop: the unsorted range is [i, n-1]
for (int i = 0; i < n - 1; i++) {
// Inner loop: find the smallest element in the unsorted range
int k = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[k])
k = j; // Record the index of the smallest element
}
// Swap the smallest element with the first element of the unsorted range
(nums[k], nums[i]) = (nums[i], nums[k]);
}
}
selection_sort.go
/* Selection sort */
func selectionSort(nums []int) {
n := len(nums)
// Outer loop: the unsorted range is [i, n-1]
for i := 0; i < n-1; i++ {
// Inner loop: find the smallest element in the unsorted range
k := i
for j := i + 1; j < n; j++ {
if nums[j] < nums[k] {
// Record the index of the smallest element
k = j
}
}
// Swap the smallest element with the first element of the unsorted range
nums[i], nums[k] = nums[k], nums[i]
}
}
selection_sort.swift
/* Selection sort */
func selectionSort(nums: inout [Int]) {
// Outer loop: the unsorted range is [i, n-1]
for i in nums.indices.dropLast() {
// Inner loop: find the smallest element in the unsorted range
var k = i
for j in nums.indices.dropFirst(i + 1) {
if nums[j] < nums[k] {
k = j // Record the index of the smallest element
}
}
// Swap the smallest element with the first element of the unsorted range
nums.swapAt(i, k)
}
}
selection_sort.js
/* Selection sort */
function selectionSort(nums) {
let n = nums.length;
// Outer loop: the unsorted range is [i, n-1]
for (let i = 0; i < n - 1; i++) {
// Inner loop: find the smallest element in the unsorted range
let k = i;
for (let j = i + 1; j < n; j++) {
if (nums[j] < nums[k]) {
k = j; // Record the index of the smallest element
}
}
// Swap the smallest element with the first element of the unsorted range
[nums[i], nums[k]] = [nums[k], nums[i]];
}
}
selection_sort.ts
/* Selection sort */
function selectionSort(nums: number[]): void {
let n = nums.length;
// Outer loop: the unsorted range is [i, n-1]
for (let i = 0; i < n - 1; i++) {
// Inner loop: find the smallest element in the unsorted range
let k = i;
for (let j = i + 1; j < n; j++) {
if (nums[j] < nums[k]) {
k = j; // Record the index of the smallest element
}
}
// Swap the smallest element with the first element of the unsorted range
[nums[i], nums[k]] = [nums[k], nums[i]];
}
}
selection_sort.dart
/* Selection sort */
void selectionSort(List<int> nums) {
int n = nums.length;
// Outer loop: the unsorted range is [i, n-1]
for (int i = 0; i < n - 1; i++) {
// Inner loop: find the smallest element in the unsorted range
int k = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[k]) k = j; // Record the index of the smallest element
}
// Swap the smallest element with the first element of the unsorted range
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
}
}
selection_sort.rs
/* Selection sort */
fn selection_sort(nums: &mut [i32]) {
if nums.is_empty() {
return;
}
let n = nums.len();
// Outer loop: the unsorted range is [i, n-1]
for i in 0..n - 1 {
// Inner loop: find the smallest element in the unsorted range
let mut k = i;
for j in i + 1..n {
if nums[j] < nums[k] {
k = j; // Record the index of the smallest element
}
}
// Swap the smallest element with the first element of the unsorted range
nums.swap(i, k);
}
}
selection_sort.c
/* Selection sort */
void selectionSort(int nums[], int n) {
// Outer loop: the unsorted range is [i, n-1]
for (int i = 0; i < n - 1; i++) {
// Inner loop: find the smallest element in the unsorted range
int k = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[k])
k = j; // Record the index of the smallest element
}
// Swap the smallest element with the first element of the unsorted range
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
}
}
selection_sort.kt
/* Selection sort */
fun selectionSort(nums: IntArray) {
val n = nums.size
// Outer loop: the unsorted range is [i, n-1]
for (i in 0..<n - 1) {
var k = i
// Inner loop: find the smallest element in the unsorted range
for (j in i + 1..<n) {
if (nums[j] < nums[k])
k = j // Record the index of the smallest element
}
// Swap the smallest element with the first element of the unsorted range
val temp = nums[i]
nums[i] = nums[k]
nums[k] = temp
}
}
selection_sort.rb
### Selection sort ###
def selection_sort(nums)
n = nums.length
# Outer loop: the unsorted range is [i, n-1]
for i in 0...(n - 1)
# Inner loop: find the smallest element in the unsorted range
k = i
for j in (i + 1)...n
if nums[j] < nums[k]
k = j # Record the index of the smallest element
end
end
# Swap the smallest element with the first element of the unsorted range
nums[i], nums[k] = nums[k], nums[i]
end
end
Visualize execution
11.2.1 Algorithm properties¶
- Time complexity: \(O(n^2)\); not adaptive. The outer loop runs \(n - 1\) times. The inner loop runs \(n - 1\) times in the first round and \(1\) time in the last, giving successive counts of \(n - 1\), \(n - 2\), \(\dots\), \(2\), and \(1\), which sum to \(\frac{n(n - 1)}{2}\).
- Space complexity: \(O(1)\); in-place. Pointers \(i\) and \(j\) use constant extra space.
- Not stable. As shown below,
nums[i]may be swapped to the right of an equal element, changing their relative order.

Figure 11-3 An example showing that selection sort is not stable