Number of Comparisons in Straight Selection Sort

1. Introduction

In this tutorial, we’ll determine the number of comparisons in Straight Selection Sort.

2. Problem Statement

We have an input array $a$ with $n$ elements that can be of any type: integers, floats, strings, or more complex objects. Our goal is to determine the number of comparisons the Straight Selection Sort algorithm will make to sort the input array non-decreasingly. The result will also hold for the non-increasing order.

2.1. Straight Selection Sort

Straight Selection Sort iteratively grows a sorted sub-array at the beginning of $a$ . In the $i$ -th pass over $a$ , it selects the smallest element of $a[i..n]$ and puts it at the $i$ -th position in $a$ . Iterating over $\boldsymbol{a[i..n]}$ , Straight Selection Sort remembers the index of the minimal element and swaps it with $\boldsymbol{a[i]}$ at the end of the $\boldsymbol{i}$ -th pass.

Here’s the pseudocode:

The number of exchanges is $n-1$ since only one swap happens per outer loop’s iteration. What goes on with the number of comparisons?

3. The Formula for the Number of Comparisons

In the first iteration of the outer loop, only $a[1]$ isn’t compared to another element. For each $j = 2, 3, \ldots, n$ , there is one comparison. So, the algorithm makes $n-1$ comparisons in the first iteration in total.

Similarly, it makes $n-2$ comparisons in the second outer iteration, $n-3$ in the third one, and so on, until the $n$ -th pass. Since there are $n$ elements in the array, there is none to which we can compare $a[n]$ . So, there are no comparisons in the final iteration.

From there, we see that Straight Selection Sorts performs $\boldsymbol{n - i}$ comparisons in the $\boldsymbol{i}$ -th iteration of the outer loop ( $i=1,2,\ldots,n$ ). As a result, the total number of comparisons is:

(1) $\begin{equation*} \sum_{i=1}^{n}(n-i) = (n-1) + (n-2) + \ldots + 2 + 1 + 0 = \sum_{i=0}^{n-1}i = \frac{n(n-1)}{2} \in O(n^2) \end{equation*}$

Since we didn’t assume anything about the input array, this formula holds no matter its structure. Even if $a$ is already sorted, Straight Selection Sort will perform $\frac{n(n-1)}{2}$ comparisons.

That’s the reason the algorithm is of quadratic time complexity. Although the number of swaps is $n-1 \in O(n)$ , the comparisons make Straight Selection Sort quadratic.

4. Conclusion

In this article, we calculated the number of comparisons in Straight Selection Sort. If the input array has $\boldsymbol{n}$ elements, the algorithm will perform $\boldsymbol{\frac{n(n-1)}{2}}$ comparisons no matter what the array is like.

Full Archive

About Baeldung

1. Introduction

2. Problem Statement

2.1. Straight Selection Sort

3. The Formula for the Number of Comparisons

4. Conclusion