Care este complexitatea temporală a sortării cu bule?

În cele mai rele și medii cazuri, complexitatea temporară este $O(n^2)$, unde $n$ este numărul de elemente din listă. În cel mai bun caz (când lista este deja sortată), este $O(n)$.

# Funcție de sortare cu bule
def bubble_sort(arr):
    n = len(arr)
    # Parcurgem toate elementele array-ului
    for i in range(n):
        # Flag pentru optimizare: dacă în o trecere nu au fost schimbări, lista este sortată
        swapped = False
        # Ultimele i elemente sunt deja la locul lor
        for j in range(0, n-i-1):
            # Dacă elementul curent este mai mare decât următorul, le schimbăm
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # Dacă în o trecere nu au fost schimbări, ieșim
        if not swapped:
            break
    return arr

# Exemple de utilizare
# Cazul cel mai rău (listă sortată invers)
arr_worst = [5, 4, 3, 2, 1]
bubble_sort(arr_worst) # Se efectuează n*(n-1)/2 comparații și schimbări

# Cazul mediu (listă aleatorie)
arr_average = [3, 1, 4, 1, 5, 9, 2, 6]
bubble_sort(arr_average) # În medie, numărul de comparații și schimbări este proporțional cu n^2

# Cazul cel mai bun (listă sortată)
arr_best = [1, 2, 3, 4, 5]
bubble_sort(arr_best) # Datorită optimizării, se face doar o singură trecere, cu n comparații

Scenariu	Complexitate temporară
Cazul cel mai rău	$O(n^2)$
Cazul mediu	$O(n^2)$
Cazul cel mai bun	$O(n)$