Skip to content

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.

  1. Initially, all elements are unsorted, so the unsorted index interval is \([0, n-1]\).
  2. Select the smallest element in \([0, n-1]\) and swap it with the element at index \(0\). The first element is now sorted.
  3. Select the smallest element in \([1, n-1]\) and swap it with the element at index \(1\). The first two elements are now sorted.
  4. Continue in this way. After \(n - 1\) rounds of selection and swapping, the first \(n - 1\) elements are sorted.
  5. The remaining element must be the largest and needs no sorting. The array is now sorted.

Steps of selection sort

selection_sort_step2

selection_sort_step3

selection_sort_step4

selection_sort_step5

selection_sort_step6

selection_sort_step7

selection_sort_step8

selection_sort_step9

selection_sort_step10

selection_sort_step11

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.

An example showing that selection sort is not stable

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

Share your insights, questions, or suggestions in the comments