选择排序是稳定的吗？

1. Introduction

In this tutorial, we’ll see if Selection Sort is a stable or unstable algorithm.

2. Stable Sorting Algorithms

A sorting algorithm is stable if it keeps the relative order of equal elements.

For example, let be the array to sort. If a[1]=a[4] , then a stable algorithm will place the item a[1] before the item a[4] in the sorted output.

2.1. Example

Let’s say that we want to sort a word array:

$[ a = [\textcolor{baeldungblue}{Dog}, Mouse, \textcolor{baeldungred}{Dog}, Cat]]$

It contains two equal elements: the blue and the red Dog . A stable sorting algorithm would put the blue Dog before the red one in the sorted output because that’s their order in the input array:

$[ a = [Cat, \textcolor{baeldungblue}{Dog}, \textcolor{baeldungred}{Dog}, Mouse]]$

Would Selection Sort do that? Is it a stable or unstable sorting algorithm?

3. The Standard Selection Sort Is Not Stable

Here’s the pseudocode of the usual formulation of Selection Sort:

algorithm SelectionSort(a, n):
    // INPUT
    //    a = the input array with n elements
    // OUTPUT
    //    a is sorted non-decreasingly (a[1] ≤ a[2] ≤ ... ≤ a[n-1] ≤ a[n])

    // The outer loop invariant is that a[1 : (i-1)] is sorted
    for i <- 1 to n:
        // Find the index of the minimal element in the sub-array a[i : n]
        j_min <- i
        for j <- i to n:
            if a[j] < a[j_min]:
                j_min <- j
        
        // Exchange a[j_min] with a[i] if necessary
        if i != j_min:
            temp <- a[i]
            a[i] <- a[j_min]
            a[j_min] <- temp

It repeatedly places the minimal elements of $a[1..n], a[2..n], \ldots, a[n..n]$ at positions $1, 2, \ldots, n$ , swapping the minimum of a[i..n] with the element a[i] . As a result, it may place $\boldsymbol{a[i]}$ after the elements it’s equal to when it exchanges it with the minimum of $\boldsymbol{a[i..n]}$ .

3.1. Example

Let’s work show how Selection Sort would handle our animal array:

$[ a = [\textcolor{baeldungblue}{Dog}, Mouse, \textcolor{baeldungred}{Dog}, Cat]]$

In the first iteration of the outer for-loop, the algorithm determines that Cat is the minimal element and exchanges it with the blue Dog :

$[ a = [Cat, Mouse, \textcolor{baeldungred}{Dog}, \textcolor{baeldungblue}{Dog}]]$

Then, it finds that the red Dog is the minimal item in the rest of the array ( a[2..4] ) and swaps it with Mouse :

$[ a = [Cat, \textcolor{baeldungred}{Dog}, Mouse, \textcolor{baeldungblue}{Dog}]]$

Finally, since Dog < Mouse in the usual lexicographic order, Selection Sort swaps the red Dog with Mouse :

$[ a = [Cat, \textcolor{baeldungred}{Dog}, \textcolor{baeldungblue}{Dog}, Mouse]]$

As we see, that doesn’t maintain the relative order of the two strings. Since they are equal, the one that was initially before the other should come first in the output array. But, Selection Sort places the red Dog before the blue one even though their initial relative order was opposite.

So, we can conclude that the standard formulation of Selection Sort isn’t stable.

4. Can We Make a Stable Variant of Selection Sort?

Instead of swapping the minimum of a[i..n] with a[i] in the -th iteration of the outer loop, we could delete the minimum $a[j_{\min}]$ from a[i..n] and insert it between a[i-1] and a[i] , effectively shifting the unsorted items $a[i], \ldots, a[j_{\min}-1]$ one position to the right. That way, we change only place the element $a[j_{\min}]$ at the position it should take in the sorted array and don’t affect the relative order of other unsorted items.

4.1. Example

Let’s work out an example. Here’s how this new algorithm sorts the array from above:

$[ \begin{aligned} & i & \text{at the end of iteration } i &&\\ & 0 & [\textcolor{baeldungblue}{Dog}, Mouse, \textcolor{baeldungred}{Dog}, Cat] && \text{(the input, before the loop)} \\ & 1 & [Cat, \textcolor{baeldungblue}{Dog}, Mouse, \textcolor{baeldungred}{Dog}] && \\ & 2 & [Cat, \textcolor{baeldungblue}{Dog}, Mouse, \textcolor{baeldungred}{Dog}] && \\ & 3 & [Cat, \textcolor{baeldungblue}{Dog}, \textcolor{baeldungred}{Dog}, Mouse] && \end{aligned}]$

As expected, the relative order of the blue and red Dog s doesn’t change.

4.2. Pseudocode

Here’s the pseudocode:

algorithm StableSelectionSort(a, n):
    // INPUT
    //    a = the input array with n elements
    // OUTPUT
    //    a is sorted non-decreasingly (a[1] ≤ a[2] ≤ ... ≤ a[n-1] ≤ a[n])

    // The outer loop invariant is that a[1 : (i-1)] is sorted.
    for i <- 1 to n:
        // Find the index of the minimal element in the sub-array a[i : n].
        j_min <- i
        for j <- i to n:
            if a[j] < a[j_min]:
                j_min <- j

        // If j_min != i, place a[j_min] at the i-th position 
        // and shift the rest of unsorted elements one position to the right up to j_min.
        if i != j_min:
            temp <- a[j_min]
            for j <- j_min to i + 1: // step -1
                a[j] <- a[j-1]
            a[i] <- temp 

    return a

4.3. Is This a Selection Sort?

The problem is that insertions and shifts aren’t present in the standard formulation of Selection Sort, only the exchanges. So, we could say that the algorithm we’ve just described isn’t a variant of Selection Sort.

However, there’s also ground to argue that it is. It preserves the main idea of Selection Sort: grow a sorted sub-array at the beginning of the array by repeatedly selecting the minimal elements of the unsorted part and placing them right at the end of the sorted sub-array. If we take that perspective, the insertions and shifts are nothing more than implementation details. Hence, they don’t change the logic, so the algorithm is a legitimate variant of Selection Sort.

4.4. Stable Selection Sort and Linked Lists

The problem with this Shift Selection Sort of ours is that, although stable, it does a lot of shifting. In the worst case, the minimal element $a[j_{\min}]$ will always be at the last position (), which happens when the array is sorted non-increasingly at the input. If that’s the case, there will be n-i shifts in each outer loop’s iteration, which brings us to O(n^2) shifts in total:

$[\sum_{i=1}^{n}(n-i) = (n-1) + (n-2) + \ldots + 2 + 1 + 0 = 0 + 1 + 2 + \ldots + (n-1) + (n-2) = \sum_{i=0}^{n-1}i = \frac{n(n-1)}{2} \in O(n^2)]$

That doesn’t make the time complexity worse compared with the standard formulation. But, it adds a computational burden that’s making the algorithm less efficient in practice.

A solution is to convert the array to a linked list. In that case, we don’t need to shift the elements. The only thing we need to do is redirect the pointer of a[i-1] to $a[j_{\min}]$ and the pointer of $a[j_{\min}]$ to a[i] .

5. Conclusion

In this article, we talked about the stability of Selection Sort. When applied to arrays, its standard formulation is unstable. However, we can modify it to be stable on both array and linked-list inputs.

Persistence

REST

Security