Ako určiť časovú zložitosť algoritmu bublinkového triedenia?

Časová zložitosť algoritmu bublinkového triedenia je určená počtom porovnaní a výmen, ktoré vykonáva.

Bublinkové triedenie prechádza cez pole niekoľkokrát, pri každej iterácii porovnáva susedné prvky a vymieňa ich, ak sú v nesprávnom poradí.

• V najhoršom a priemernom prípade algoritmus vykoná približne n-1 prechodov cez pole s n prvkami.
• Pri každom prechode sa vykoná až n-1 porovnanie.

Celkovo je časová zložitosť O(n²).

Príklad:

for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            std::swap(arr[j], arr[j + 1]);
        }
    }
}

Preto je algoritmus neefektívny pre veľké polia kvôli svojej kvadratickej zložitosti.