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

Description

Element number n gets inserted at the proper position and all already inserted (indices 0..n-1) elements get moved one position.

Algorithm

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

Analysis

Mmin=0M_{min} = 0

Mmax=(n2n)/2M_{max} = (n^2 - n) / 2

Mavg=(n2n)/4M_{avg} = (n^2 - n) / 4

O(n2)O(n^2)

Cmin=n1C_{min} = n - 1

Cmax=(n2n)/2C_{max} = (n^2 - n) / 2

Cavg=(n2+3n4)/4C_{avg} = (n^2 + 3n - 4) / 4

O(n2)O(n^2)