Mi a buborékrendezés időbeli komplexitása?

A legrosszabb és közepes esetekben az időbonyolultság $O(n^2)$, ahol $n$ a lista elemeinek száma. A legjobb esetben (amikor a lista már rendezett), ez $O(n)$.

# Buborékrendező függvény
def bubble_sort(arr):
    n = len(arr)
    # Az összes elem átvizsgálása
    for i in range(n):
        # Jelző az optimalizáláshoz: ha egy átmenet során nem volt csere, a lista rendezett
        swapped = False
        # Az utolsó i elem már a helyén
        for j in range(0, n-i-1):
            # Ha az aktuális elem nagyobb, mint a következő, cseréljük
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # Ha egy átmenet során nem volt csere, kilépünk
        if not swapped:
            break
    return arr

# Használati példák
# Legrosszabb eset (fordított sorrendű lista)
arr_worst = [5, 4, 3, 2, 1]
bubble_sort(arr_worst) # n*(n-1)/2 összehasonlítás és csere történik

# Átlagos eset (véletlenszerű lista)
arr_average = [3, 1, 4, 1, 5, 9, 2, 6]
bubble_sort(arr_average) # Átlagosan a összehasonlítások és cserék száma is arányos n^2-vel

# Legjobb eset (rendezett lista)
arr_best = [1, 2, 3, 4, 5]
bubble_sort(arr_best) # Az optimalizációnak köszönhetően csak egy átmenet történik, n összehasonlítással

Szcenárió	Időbonyolultság
Legrosszabb eset	$O(n^2)$
Átlagos eset	$O(n^2)$
Legjobb eset	$O(n)$