Skip to content
Welcome to contribute to Chinese-to-English translation! For more details, please refer to CONTRIBUTING.md.

# 11.2 Selection Sort

Selection sort works very simply: in each round, it selects the smallest element from the unsorted interval and places it at the end of the sorted interval.

Assume the array has length \(n\). The procedure of selection sort is shown in Figure 11-2.

1. Initially, all elements are unsorted, i.e., the unsorted (index) interval is \([0, n-1]\).
2. Select the smallest element in the interval \([0, n-1]\) and swap it with the element at index \(0\). After completion, the first element of the array is sorted.
3. Select the smallest element in the interval \([1, n-1]\) and swap it with the element at index \(1\). After completion, the first 2 elements of the array are sorted.
4. And so on. After \(n - 1\) rounds of selection and swapping, the first \(n - 1\) elements of the array are sorted.
5. The only remaining element must be the largest, so no further sorting is needed and the array is sorted.

<1><2><3><4><5><6><7><8><9><10><11>

Figure 11-2 Selection sort steps

In the code, we use \(k\) to track the smallest element within the unsorted interval:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
selection_sort.py

    def selection_sort(nums: list[int]):
        """Selection sort"""
        n = len(nums)
        # Outer loop: unsorted interval is [i, n-1]
        for i in range(n - 1):
            # Inner loop: find the smallest element within the unsorted interval
            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 interval
            nums[i], nums[k] = nums[k], nums[i]

selection_sort.cpp

    /* Selection sort */
    void selectionSort(vector<int> &nums) {
        int n = nums.size();
        // Outer loop: unsorted interval is [i, n-1]
        for (int i = 0; i < n - 1; i++) {
            // Inner loop: find the smallest element within the unsorted interval
            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 interval
            swap(nums[i], nums[k]);
        }
    }

selection_sort.java

    /* Selection sort */
    void selectionSort(int[] nums) {
        int n = nums.length;
        // Outer loop: unsorted interval is [i, n-1]
        for (int i = 0; i < n - 1; i++) {
            // Inner loop: find the smallest element within the unsorted interval
            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 interval
            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: unsorted interval is [i, n-1]
        for (int i = 0; i < n - 1; i++) {
            // Inner loop: find the smallest element within the unsorted interval
            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 interval
            (nums[k], nums[i]) = (nums[i], nums[k]);
        }
    }

selection_sort.go

    /* Selection sort */
    func selectionSort(nums []int) {
        n := len(nums)
        // Outer loop: unsorted interval is [i, n-1]
        for i := 0; i < n-1; i++ {
            // Inner loop: find the smallest element within the unsorted interval
            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 interval
            nums[i], nums[k] = nums[k], nums[i]

        }
    }

selection_sort.swift

    /* Selection sort */
    func selectionSort(nums: inout [Int]) {
        // Outer loop: unsorted interval is [i, n-1]
        for i in nums.indices.dropLast() {
            // Inner loop: find the smallest element within the unsorted interval
            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 interval
            nums.swapAt(i, k)
        }
    }

selection_sort.js

    /* Selection sort */
    function selectionSort(nums) {
        let n = nums.length;
        // Outer loop: unsorted interval is [i, n-1]
        for (let i = 0; i < n - 1; i++) {
            // Inner loop: find the smallest element within the unsorted interval
            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 interval
            [nums[i], nums[k]] = [nums[k], nums[i]];
        }
    }

selection_sort.ts

    /* Selection sort */
    function selectionSort(nums: number[]): void {
        let n = nums.length;
        // Outer loop: unsorted interval is [i, n-1]
        for (let i = 0; i < n - 1; i++) {
            // Inner loop: find the smallest element within the unsorted interval
            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 interval
            [nums[i], nums[k]] = [nums[k], nums[i]];
        }
    }

selection_sort.dart

    /* Selection sort */
    void selectionSort(List<int> nums) {
      int n = nums.length;
      // Outer loop: unsorted interval is [i, n-1]
      for (int i = 0; i < n - 1; i++) {
        // Inner loop: find the smallest element within the unsorted interval
        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 interval
        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: unsorted interval is [i, n-1]
        for i in 0..n - 1 {
            // Inner loop: find the smallest element within the unsorted interval
            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 interval
            nums.swap(i, k);
        }
    }

selection_sort.c

    /* Selection sort */
    void selectionSort(int nums[], int n) {
        // Outer loop: unsorted interval is [i, n-1]
        for (int i = 0; i < n - 1; i++) {
            // Inner loop: find the smallest element within the unsorted interval
            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 interval
            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: unsorted interval is [i, n-1]
        for (i in 0..<n - 1) {
            var k = i
            // Inner loop: find the smallest element within the unsorted interval
            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 interval
            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: unsorted interval is [i, n-1]
      for i in 0...(n - 1)
        # Inner loop: find the smallest element within the unsorted interval
        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 interval
        nums[i], nums[k] = nums[k], nums[i]
      end
    end

## 11.2.1 Algorithm Characteristics

- Time complexity \(O(n^2)\), non-adaptive sorting: The outer loop has \(n - 1\) rounds in total. The inner loop runs \(n - 1\) times in the first round and \(1\) time in the last round. Thus, it runs \(n - 1\), \(n - 2\), \(\dots\), \(2\), and \(1\) times across the rounds, summing to \(\frac{n(n - 1)}{2}\).
- Space complexity \(O(1)\), in-place sorting: Pointers \(i\) and \(j\) use a constant amount of extra space.
- Unstable sorting: As shown in Figure 11-3, element `nums[i]` may be swapped to the right of an element equal to it, causing a change in their relative order.

Figure 11-3 Selection sort non-stability example

##### Feel free to drop your insights, questions or suggestions