Explore Selection Sort in Depth

Prerequisite Knowledge

Before reading this article, you should first learn:

• Key Metrics of Sorting Algorithms

Summary in One Sentence

Selection sort is the simplest and most straightforward sorting algorithm, but it has a high time complexity and is not a stable sort. Other basic sorting algorithms are optimizations based on selection sort.

If you are a beginner who hasn't encountered sorting algorithms yet, that's great! Don't rush to look at definitions and such. If you have previously learned about sorting algorithms, please forget the definitions and the algorithm code you memorized.

With the foundation laid earlier, you already have some programming skills and can solve basic algorithm problems. With that in mind, here's a learning method I would like to share with you:

When faced with a new problem, don't rush to ask someone for a standard answer. Instead, start thinking for yourself. Being spoon-fed a standard answer once is a missed opportunity and diminishes your creativity.

There are always some readers who come to me with a worried face, complaining about forgetting algorithm problems after practicing them. I actually think this is a good thing. Remembering everything is an obsession; forgetting is good because it means you're not yet full, which is an opportunity for independent thinking.

So, let's seize this opportunity. Now, imagine you have an array of numbers, and you're asked to write a sorting algorithm to arrange all elements from smallest to largest. How would you do it? If you've never thought about this before, take a few minutes to consider it.

void sort(int[] nums) {
    // your code to sort the elements in nums in ascending order
}

The first time I thought about this problem, the most straightforward method that came to mind was this:

First, go through the array to find the smallest value and swap it with the first element of the array. Then, iterate through the array again to find the second smallest element and swap it with the second element of the array. Continue this process until the entire array is sorted.

This algorithm is commonly known as "Selection Sort," where you repeatedly traverse to select the smallest element. Here is how it looks in code:

java

void sort(int[] nums) {
    int n = nums.length;
    // sortedIndex is a delimiter
    // elements with index < sortedIndex are sorted
    // elements with index >= sortedIndex are unsorted
    // initialized to 0, indicating the whole array is unsorted
    int sortedIndex = 0;
    while (sortedIndex < n) {
        // find the minimum in the unsorted part [sortedIndex, n)
        int minIndex = sortedIndex;
        for (int i = sortedIndex + 1; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }
        // swap the minimum value with the element at sortedIndex
        int tmp = nums[sortedIndex];
        nums[sortedIndex] = nums[minIndex];
        nums[minIndex] = tmp;

        // move sortedIndex one position forward
        sortedIndex++;
    }
}

cpp

void sort(vector<int>& nums) {
    int n = nums.size();
    // sortedIndex is a dividing line
    // elements with index < sortedIndex are all sorted
    // elements with index >= sortedIndex are all unsorted
    // initialize to 0, meaning the entire array is unsorted
    int sortedIndex = 0;
    while (sortedIndex < n) {
        // find the minimum value in the unsorted part [sortedIndex, n)
        int minIndex = sortedIndex;
        for (int i = sortedIndex + 1; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }
        // swap the minimum value with the element at sortedIndex
        int tmp = nums[sortedIndex];
        nums[sortedIndex] = nums[minIndex];
        nums[minIndex] = tmp;

        // move sortedIndex forward by one
        sortedIndex++;
    }
}

python

def sort(nums: List[int]) -> None:
    n = len(nums)
    # sortedIndex is a boundary
    # elements with index < sortedIndex are sorted
    # elements with index >= sortedIndex are unsorted
    # initialized to 0, meaning the whole array is unsorted
    sortedIndex = 0
    while sortedIndex < n:
        # find the minimum in the unsorted part [sortedIndex, n)
        minIndex = sortedIndex
        for i in range(sortedIndex + 1, n):
            if nums[i] < nums[minIndex]:
                minIndex = i
        # swap the minimum value with the element at sortedIndex
        nums[sortedIndex], nums[minIndex] = nums[minIndex], nums[sortedIndex]

        # increment sortedIndex by one
        sortedIndex += 1

go

func sort(nums []int) {
    n := len(nums)
    // sortedIndex is a partition line
    // elements with index < sortedIndex are sorted
    // elements with index >= sortedIndex are unsorted
    // initialized to 0, indicating the entire array is unsorted
    sortedIndex := 0
    for sortedIndex < n {
        // find the minimum value in the unsorted part [sortedIndex, n)
        minIndex := sortedIndex
        for i := sortedIndex + 1; i < n; i++ {
            if nums[i] < nums[minIndex] {
                minIndex = i
            }
        }
        // swap the minimum value with the element at sortedIndex
        nums[sortedIndex], nums[minIndex] = nums[minIndex], nums[sortedIndex]

        // move sortedIndex one position forward
        sortedIndex++
    }
}

javascript

function sort(nums) {
    const n = nums.length;
    // sortedIndex is a delimiter
    // elements with index < sortedIndex are sorted
    // elements with index >= sortedIndex are unsorted
    // initialized to 0, indicating the entire array is unsorted
    let sortedIndex = 0;
    while (sortedIndex < n) {
        // find the index of the minimum value in the unsorted part [sortedIndex, n)
        let minIndex = sortedIndex;
        for (let i = sortedIndex + 1; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }
        // swap the minimum value with the element at sortedIndex
        [nums[sortedIndex], nums[minIndex]] = [nums[minIndex], nums[sortedIndex]];

        // move sortedIndex one position forward
        sortedIndex++;
    }
}

The visualization of the above algorithm is as follows:

This algorithm is correct and can be slightly modified to serve as the solution for LeetCode Problem 912 "Sort an Array."

However, this algorithm cannot pass all test cases for Problem 912. It eventually results in a timeout error, indicating that while the logic is correct, the time complexity is too high and exceeds the problem's limits.

For now, let's set aside how to pass Problem 912 and analyze this sorting algorithm based on several key metrics of sorting algorithms.

Is it an in-place sort?

Yes. The algorithm doesn't use additional array space for assistance, only a few variables, so the space complexity is O(1).

Time and Space Complexity Analysis

The sort function includes a while loop nested within a for loop, which can be represented as follows:

for (int sortedIndex = 0; sortedIndex < n; sortedIndex++) {
    for (int i = sortedIndex + 1; i < n; i++) {
        // ...
    }
}

As you can see, this is a nested for loop. The total number of iterations is (n - 1) + (n - 2) + (n - 3) +... + 1, which is an arithmetic series sum. The result is approximately n^2 / 2, so the time complexity of this sorting algorithm, expressed in Big O notation, is O(n^2), where n is the number of elements in the array to be sorted.

Moreover, notice that this algorithm has a characteristic: even if the entire array is already sorted, it will still execute n^2 / 2 times, meaning the initial order of the data does not affect the time complexity of the algorithm.

Pay Attention to Actual Execution Count of Sorting Algorithms

For general algorithm time and space complexity analysis, we usually analyze from the perspective of Big O notation, focusing only on the order of magnitude (the highest power term) and not on coefficients or lower-order terms.

However, when analyzing different sorting algorithms, it is necessary to consider the actual execution count and certain special cases (such as when the array is already sorted).

Since multiple sorting algorithms have a complexity of O(n^2) from a Big O perspective, we need to evaluate their strengths and weaknesses based on their actual execution count and performance in special cases.

Where Does the Time Go? Optimization Ideas?

Now, take a moment to observe the logic of this algorithm and think carefully for a few minutes: is there any possibility to optimize the time complexity?

Don't underestimate this basic chapter. The thought process I discuss here is the same for any problem you'll face in the future when optimizing time complexity.

First, if the code is correct but the algorithm's time complexity is still too high, there's only one possibility: there is redundant computation.

The redundancy in the above algorithm is quite obvious:

It first traverses nums[0..] to find the minimum value, then traverses nums[1..] to find the minimum, and then nums[2..], and so on.

But when you traverse nums[0..], you've already gone through all the elements of nums[1..] and nums[2..]. Why traverse them again?

In theory, you should be able to find the minimum elements of nums[1..] and nums[2..] while traversing nums[0..], right? If you can do this, wouldn't it eliminate the inner for loop and reduce the time complexity by one order?

Now, we've identified the root of the redundant computation and have an optimization idea. Can this idea be implemented? Can you find the minimum elements of nums[1..] and nums[2..] while traversing nums[0..]?

I will abstract this and transform the optimization scenario into a new problem:

Given an array nums, calculate a new array suffixMin where suffixMin[i] represents the minimum value in nums[i..].

If you think forward, if I know the minimum element in nums[0..], can I deduce the minimum in nums[1..]?

The answer is no. There's not enough information to deduce min(nums[1..]) from min(nums[0..]), so you'd have to traverse nums[1..] again.

But it seems unbelievable that calculating a minimum value is so difficult. Is my brain locked by some invisible force??

If you think backward, if I know the minimum element in nums[1..], can I deduce the minimum in nums[0..]?

The answer is yes, min(nums[0..]) = min(nums[0], min(nums[1..])).

With this idea, you can calculate the suffixMin array by working backward:

int[] nums = new int[]{3, 1, 4, 2};
// suffixMin[i] indicates the minimum value in nums[i..]
int[] suffixMin = new int[nums.length];

// calculate suffixMin from back to front
suffixMin[nums.length - 1] = nums[nums.length - 1];
for (int i = nums.length - 2; i >= 0; i--) {
    suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);
}

// [1, 1, 2, 2]
System.out.println(suffixMin);

Alright, we've solved the problem of calculating the suffixMin array. Now, let's return to optimizing selection sort. I only need to spend O(n) time to traverse the nums array once to calculate the suffixMin array, which allows me to get the minimum value of any subarray like nums[1..], nums[2..], ... in O(1) time.

Logically, I should be able to eliminate the inner for loop of the selection sort and optimize the time complexity to O(n), right? The answer is no.

Take a few minutes to think about why this doesn't work. What is the crucial issue here?

Click to see my thoughts

Some readers might say that in selection sort, you need to know the index of the minimum element to perform a swap, and the suffixMin array only stores the value of the minimum element, not the index, so it can't optimize selection sort.

However, I can easily create a new array minIndex that records the index of the minimum element while calculating the suffixMin array, so this is not the key issue.

The real key issue is the swap operation.

The suffixMin array works correctly only under the condition that the nums array is immutable. If the value of nums[i] changes, then the values in suffixMin[0..i] might all become invalid and need to be recalculated.

The swap operation in selection sort changes the positions of elements in nums, causing the suffixMin array to become invalid. This is the core of the problem.

In conclusion, all attempts are incorrect, and selection sort cannot be optimized in any way.

Some readers might wonder if spending so much time trying various methods only to achieve nothing is a failure.

No, I believe this is effective thinking that truly helps readers grasp algorithmic thinking. In the tutorials on this site, I often showcase this thought process, hoping you can explore and think independently as well.

For the sorting algorithms discussed later, you can also consider what fundamentally distinguishes them from selection sort. Why can they reduce the time complexity below O(n^2)?

Stability of Sorting

According to the definition of sorting stability in Key Indicators of Sorting Algorithms, analyze whether this algorithm is stable.

If this algorithm is not stable, what operation causes it to lose its stability? Can it be optimized to become stable? Take a few minutes to think about it before reading my understanding.

Click to see the answer

Selection sort is not a stable sorting algorithm.

According to the definition of stable sorting, the relative position of identical elements should not change. A simple example will show you why this algorithm is unstable:

[2', 2''', 2'', 1]

In this example, there are multiple duplicate elements 2. I use 2', 2''', and 2'' to distinguish these three elements. If this sorting algorithm is stable, then the sorted result should maintain the relative order of the three 2s:

[1, 2', 2''', 2'']

In reality, if you mentally run through this algorithm, it's not hard to realize that when it first searches for the minimum value, it will definitely swap the elements 2' and 1. This will disrupt the relative order between the 2s:

[1, 2''', 2'', 2']

The swap operation causes selection sort to lose its stability.

Is there a way to optimize this algorithm to make it a stable sort? The time complexity is already O(n^2), which is among the worst for sorting algorithms. Can we at least make it stable?

Think about this question yourself. In the upcoming sorting algorithms, we will try to solve this issue.