programming / C++ / sailing / nerd stuff
Algorithm: Selection Sort

## Description

Greatest (or smallest) element gets moved from interval `(i+1)..n` to position `i`.

• stable
• runtime almost immune against modification of the input data.

## Algorithm

 ```1 2 3 4 5 6 7 8 9 ``` ``````for (int i = 0; i < (array.count()-1); ++i) { int min = i; for (int j = i+1; j < array.count(); ++j) { if (array[j] < array[min]) { min = j; } } array.swap( min, i ); }``````

## Analysis

$M_{min} = M_{max} = M_{avg} = n - 1$

$O(n)$

$C_{min} = C_{max} = C_{avg} = (n^2 - n) / 2$

$O(n^2)$