11.2 Selection sort¶
Selection sort works on a very simple principle: it uses a loop where each iteration selects the smallest element from the unsorted interval and moves it to the end of the sorted section.
Suppose the length of the array is \(n\), the steps of selection sort is shown in Figure 11-2.
- Initially, all elements are unsorted, i.e., the unsorted (index) interval is \([0, n-1]\).
- Select the smallest element in the interval \([0, n-1]\) and swap it with the element at index \(0\). After this, the first element of the array is sorted.
- Select the smallest element in the interval \([1, n-1]\) and swap it with the element at index \(1\). After this, the first two elements of the array are sorted.
- Continue in this manner. After \(n - 1\) rounds of selection and swapping, the first \(n - 1\) elements are sorted.
- The only remaining element is subsequently the largest element and does not need sorting, thus the array is sorted.
Figure 11-2 Selection sort process
In the code, we use \(k\) to record the smallest element within the unsorted interval:
selection_sort.py
def selection_sort(nums: list[int]):
"""Selection sort"""
n = len(nums)
# Outer loop: unsorted range is [i, n-1]
for i in range(n - 1):
# Inner loop: find the smallest element within 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: unsorted range is [i, n-1]
for (int i = 0; i < n - 1; i++) {
// Inner loop: find the smallest element within 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: unsorted range is [i, n-1]
for (int i = 0; i < n - 1; i++) {
// Inner loop: find the smallest element within 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;
}
}
11.2.1 Algorithm characteristics¶
- Time complexity of \(O(n^2)\), non-adaptive sort: There are \(n - 1\) iterations in the outer loop, with the length of the unsorted section starting at \(n\) in the first iteration and decreasing to \(2\) in the last iteration, i.e., each outer loop iterations contain \(n\), \(n - 1\), \(\dots\), \(3\), \(2\) inner loop iterations respectively, summing up to \(\frac{(n - 1)(n + 2)}{2}\).
- Space complexity of \(O(1)\), in-place sort: Uses constant extra space with pointers \(i\) and \(j\).
- Non-stable sort: As shown in Figure 11-3, an element
nums[i]may be swapped to the right of an equal element, causing their relative order to change.
Figure 11-3 Selection sort instability example