Explore Selection Sort in Depth

If you are a beginner who has never been exposed to sorting algorithms, that's great; don't rush to look at definitions or similar materials. If you have studied sorting algorithms before, now please forget the definitions and the algorithm code you have memorized.

With the groundwork laid earlier, you have a certain level of programming ability and can solve some basic algorithm problems. On this premise, I would like to share a learning method for your reference:

When encountering a new problem, do not rush to ask someone for a standard answer. Instead, initiate your own thinking. Being spoon-fed a standard answer means missing an opportunity and losing a bit of creativity. If you are spoon-fed too often, you become dull.

There are always some readers who come to me with a worried look, complaining about forgetting algorithm problems after solving them. I actually think this is a good thing. Constant remembrance indicates obsession; forgetting is good, as it means the mind is not yet full, which is an opportunity for independent thinking.

So, returning to the issue, let's seize this opportunity. Now, given an array as input, you're asked to write a sorting algorithm to sort all elements in ascending order. How would you write it? If you have never thought about this problem before, take a few minutes to think about it now.

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:

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++;
    }
}

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++;
    }
}

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

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++
    }
}

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 process of the above algorithm is as follows:

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

However, this algorithm cannot pass all the test cases for Problem 912, eventually resulting in a timeout error. This indicates that while the algorithm's logic is correct, its time complexity is too high and exceeds the problem's constraints.

For now, let's set aside the issue of passing Problem 912 and analyze this sorting algorithm according to the key metrics of sorting algorithms.

Is it an in-place sort?

Yes. Because the algorithm does not use additional array space for assistance, only a few variables, making the space complexity $O(1)$.

Time and Space Complexity Analysis

This sort function contains a while loop nested within a for loop, similar to this:

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

As you can see, it is a nested for loop. The total number of iterations is (n - 1) + (n - 2) + (n - 3) +... + 1, which is the sum of an arithmetic series. 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, note that this algorithm has a characteristic: even if the entire array is already sorted, it will still perform n^2 / 2 operations, meaning the order of the original data does not affect the algorithm's time complexity.

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);

Now that the problem of calculating the suffixMin array is solved, 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 nums[1..], nums[2..], ... in $O(1)$ time.

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

Take a few minutes to think about why this is not possible. What is the key issue?

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

Some readers might ask, after spending so much time and trying various methods, we ended up with nothing. Isn't that a failure?

No, I believe this is effective thinking that truly helps readers grasp algorithmic thinking. Therefore, in this site's tutorials, I often showcase this thought process in hopes that you can also explore and think independently.

In the sorting algorithms discussed later, consider how they fundamentally differ from selection sort. Why can they reduce the time complexity below $O(n^2)$?

Stability of Sorting

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

If this algorithm is not stable, what operation causes it to lose stability? Is it possible to optimize this algorithm to make it stable? Think about it for a few minutes before reading my understanding.

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

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

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