# Selection Sort

## Algorithm

for i = n downto 2 do
k = 1
for j = 2 to i do
if A[j] > A[k] then
k = j
A[k] <-> A[i]

## Comparisons

The analysis is equivalent for all possible cases. There is a comparison every inner iteration no matter what.

- $\underset{i=2}{\overset{n}{\Sigma}}\underset{j=2}{\overset{i}{\Sigma}}1$
- $=\frac{(n-1)n}{2}$

## Exchanges

Once again, the anlysis holds for all possible cases. There is an exchange every outer iteration.

- $\underset{i=2}{\overset{n}{\Sigma}}1$
- $=n-1$