Kāda ir burbuļu kārtošanas laika sarežģītība?

Sliktākajos un vidējos gadījumos laika sarežģītība ir $O(n^2)$, kur $n$ ir elementu skaits sarakstā. Labākajā gadījumā (kad saraksts jau ir sakārtots), tā ir $O(n)$.

# Burbulis kārtošanas funkcija
def bubble_sort(arr):
    n = len(arr)
    # Pārlūko visus masīva elementus
    for i in range(n):
        # Optimizācijas zīme: ja vienā pārskatā nav bijušas maiņas, saraksts ir sakārtots
        swapped = False
        # Pēdējie i elementi jau ir vietā
        for j in range(0, n-i-1):
            # Ja pašreizējais elements ir lielāks par nākamo, apmainām
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # Ja pārskatā nav bijušas maiņas, iziet
        if not swapped:
            break
    return arr

# Piemēri
# Sliktākais gadījums (apgriezts sakārtots saraksts)
arr_worst = [5, 4, 3, 2, 1]
bubble_sort(arr_worst) # Veic n*(n-1)/2 salīdzinājumus un maiņas

# Vidējais gadījums (nejaušs saraksts)
arr_average = [3, 1, 4, 1, 5, 9, 2, 6]
bubble_sort(arr_average) # Vidēji, salīdzinājumu un maiņu skaits ir proporcionāls n^2

# Labākais gadījums (sakārtots saraksts)
arr_best = [1, 2, 3, 4, 5]
bubble_sort(arr_best) # Pateicoties optimizācijai, tiek veikts tikai viens pārskats, ar n salīdzinājumiem

Scenārijs	Laika sarežģītība
Sliktākais gadījums	$O(n^2)$
Vidējais gadījums	$O(n^2)$
Labākais gadījums	$O(n)$