# Selection sort

## General information

Algorithmic problem: Sorting based on pairwise comparison

Type of algorithm: loop

## Abstract view

Invariant: After $i \geq 0$ iterations: The elements at positions $|S|-i+1,\dots,|S|$ are correctly placed in sorting order.

Variant: $i$ increases by $1$.

Break condition: $i = |S| - 1$.

## Induction Basis

Abstract view: Nothing to do.

Implementation: Nothing to do.

Proof: Nothing to show.

## Induction step

Abstract view: Identify the maximum out of $S[1],\dots,S[|S|-i+1]$ and then move it, by a swap, to position $|S|-i+1$.

Implementation:

1. Set $m := 1$
2. For all $j=2,\dots,|S|-i+1$: If $S[j] \gt S[m]$ set $m := j$.
3. Swap $S[m]$ and $S[|S|-i+1]$.

Correctness: Obviously: $S[m]$ is the maximum element out of $S[1],\dots,S[j]$.

## Complexity

Statement: The asymptotic complexity is in $\Theta(T\cdot n^2)$ in the best and worst case, where $T$ is the complexity of the comparison.

Proof: The asymptotic complexity of the $i$-th iteration is in $\Theta(T\cdot(n - i))$. Therefore, the total complexity is in $\Theta\left(T\cdot\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(T\cdot\sum_{i=1}^{n-1} i \right) = \Theta\left(T\cdot\frac{n(n-1)}{2} \right) = \Theta\left(T\cdot n^2\right)$.