• Home
• Contact

Description

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

• stable

Algorithm

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

$M_{min} = 0$

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

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

⇒ $O(n^2)$

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

⇒ $O(n^2)$