mario::konrad
programming / C++ / sailing / nerd stuff
Algorithm: Selection Sort
© 2005 / Mario Konrad

Description

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

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

Mmin=Mmax=Mavg=n1M_{min} = M_{max} = M_{avg} = n - 1

O(n)O(n)

Cmin=Cmax=Cavg=(n2n)/2C_{min} = C_{max} = C_{avg} = (n^2 - n) / 2

O(n2)O(n^2)