Is Selection Sort Stable? | Baeldung on Computer Science

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 $a$ 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:

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 $i$ -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:

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 ( $n$ ), 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 $a$ 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.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex