In this tutorial, we’ll determine the number of comparisons in Straight Selection Sort.
2. Problem Statement
We have an input array with 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 . In the -th pass over , it selects the smallest element of and puts it at the -th position in . Iterating over , Straight Selection Sort remembers the index of the minimal element and swaps it with at the end of the -th pass.
Here’s the pseudocode:
The number of exchanges is 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 isn’t compared to another element. For each , there is one comparison. So, the algorithm makes comparisons in the first iteration in total.
Similarly, it makes comparisons in the second outer iteration, in the third one, and so on, until the -th pass. Since there are elements in the array, there is none to which we can compare . So, there are no comparisons in the final iteration.
From there, we see that Straight Selection Sorts performs comparisons in the -th iteration of the outer loop (). As a result, the total number of comparisons is:
Since we didn’t assume anything about the input array, this formula holds no matter its structure. Even if is already sorted, Straight Selection Sort will perform comparisons.
That’s the reason the algorithm is of quadratic time complexity. Although the number of swaps is , the comparisons make Straight Selection Sort quadratic.
In this article, we calculated the number of comparisons in Straight Selection Sort. If the input array has elements, the algorithm will perform comparisons no matter what the array is like.