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

Description

In every iteration the smallest (or greatest) element move upwards like a bubble.

Algorithm

1
2
3
4
5
6
7
for (int i = 0; i < array.count()-1; ++i) {
    for (int j = array.count()-1; j > i; --j) {
        if (array[j] < array[j-1]) {
            array.swap( j-1, 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=Cmax=Cavg=(n2n)/2C_{min} = C_{max} = C_{avg} = (n^2 - n) / 2

O(n2)O(n^2)