# Exercise 2.2.2

Consider sorting $n$ numbers in an 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 invariants 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 the
worst-case running times of selection sort in $\Theta$-notation.

## Pseudocode

```
SELECTION-SORT(A):
for i = 1 to A.length - 1
min = i
for j = i + 1 to A.length
if A[j] < A[min]
min = j
temp = A[i]
A[i] = A[min]
A[min] = temp
```

## Loop invariants

At the start of each iteration of the outer **for** loop, the subarray
$A[1..i - 1]$ contains the smallest $i - 1$ elements of the array, sorted
in nondecreasing order.

And:

At the start of each iteration of the inner **for** loop, $A[min]$ is the
smallest number in the subarray $A[i..j - 1]$.

## Why $n - 1$ elements?

In the final step, the algorithm will be left with two elements to compare. It
will store the smaller one in $A[n-1]$ and leave the larger in $A[n]$. The
final one will be the largest element of the array, since all the previous
iteration would have sorted all but the last two elements (the outer loop
invariant). If we do it $n$ times, we will end up with a redundant step that
sorts a single-element subarray.

## Running times

In the best-case time (the array is sorted), the body of the if is never
invoked. The number of operations (counting the comparison as one operation)
is:

$$ (n - 1)(\frac{n + 2}{2} + 4) $$

In the worst-case time (the array is reversed), the body of the if is invoked
on every occasion, which doubles the number of steps in the inner loop, that
is:

$$ (n - 1)(n + 6) $$

Both are clearly $\Theta(n^2)$.