# 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{\left(n-1\right)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$