Consider sorting $n$ numbers stored in array $A$ by first finding the smallest element of $A$ and exchanging it with the element in $A[1]$. Then find the second smallest element of $A$, and exchange it with $A[2]$. Continue in this manner for the first $n−1$ elements of $A$. Write pseudocode for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first $n − 1$ elements, rather than for all $n$ elements? Give the best-case and worst-case running times of selection sort in $\Theta$-notation.

Pseudocode for SELECTION-SORT(A)

Loop invariant for the pseudocode will be:

At the start of the each iteration of the outer for loop of lines 1-8, the subarray $A[1..i − 1]$ consists of $i - 1$ smallest elements of $A$, sorted in increasing order.

The algorithm needs to run for only the first $n − 1$ elements, rather than for all $n$ elements because the last iteration will compare $A[n - 1]$ with $A[n]$ and store the largest element among them (consequently largest element of the array) in the last index. So, there is no need to continue the algorithm for all the way to the last element.

For both the best-case (sorted array) and worst-case (reverse sorted array), the algorithm will anyway take one element at a time and compare it with all the other elements. So, the running times for both scenario will be $\Theta(n^2)$.

Mathematical Proof: We can calculate the cost and times for individual lines of the pseudocode as follows…

Line Cost Times
1 $c_1$ $(n - 1)$
2 $c_2$ $n$
3 $c_3$ $\sum_{j = 2}^n t_j$
4 $c_4$ $\sum_{j = 2}^n (t_j - 1)$
5 $c_5$ $\sum_{j = 2}^n (t_j - 1)$
6 $c_6$ $n$
7 $c_7$ $n$
8 $c_8$ $n$

Now, for any arbitrary value of $j$, the inner for loop (line 3-5) compare the previously computed minimum value with all elements in the subarray $A[j..n]$. So the inner for loop executes $n - j + 1$ times, i.e. $t_j = (n - j + 1)$ for $j = 2, 3, ..., n$. So, $t_2 = n - 1$, $t_3 = n - 2$, … $t_n = 1$. So,

Therefore, we can calculate the running time as follows..

For best-case scenario, as the array is already sorted, line #5 will not be executed ever. So, $c_5 = 0$. Even with that (and without that for worst-case) the expression of $T(n)$ will be reduced to the form $an^2 + bn + c$, i.e. the algorithm will run at $\Theta(n^2)$ time.