Как да определим времевата сложност на алгоритъма за сортиране с мехурчета?

Времевата сложност на алгоритъма за сортиране с мехурчета се определя от броя на сравненията и размените, които извършва.

Мехурчестото сортиране преминава през масива няколко пъти, като на всяка итерация сравнява съседните елементи и ги разменя, ако са в неправилен ред.

• В най-лошия и средния случай алгоритъмът извършва приблизително n-1 преминавания през масив от n елемента.
• На всяко преминаване се извършват до n-1 сравнения.

Общата времева сложност е O(n²).

Пример:

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]);
        }
    }
}

Следователно, алгоритъмът не е ефективен за големи масиви поради квадратичната си сложност.