Qual é a complexidade temporal da ordenação por bolha?

Nos piores e médios casos, $O(n^2)$, onde $n$ é o número de elementos na lista. No melhor caso (quando a lista já está ordenada), é $O(n)$.

# Função de ordenação bubble
 def bubble_sort(arr):
    n = len(arr)
    # Percorre todos os elementos do array
    for i in range(n):
        # Flag para otimização: se numa passagem não houve trocas, a lista está ordenada
        swapped = False
        # Os últimos i elementos já estão nos seus lugares
        for j in range(0, n-i-1):
            # Se o elemento atual for maior que o seguinte, trocamos
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # Se numa passagem não houve trocas, terminamos
        if not swapped:
            break
    return arr

# Exemplos de uso
# Caso pior (lista ordenada ao contrário)
arr_worst = [5, 4, 3, 2, 1]
bubble_sort(arr_worst) # Realiza n*(n-1)/2 comparações e trocas

# Caso médio (lista aleatória)
arr_average = [3, 1, 4, 1, 5, 9, 2, 6]
bubble_sort(arr_average) # Em média, a quantidade de comparações e trocas também é proporcional a n^2

# Melhor caso (lista ordenada)
arr_best = [1, 2, 3, 4, 5]
bubble_sort(arr_best) # Graças à otimização, realiza apenas uma passagem, com n comparações

Cenário	Complexidade temporal
Caso pior	$O(n^2)$
Caso médio	$O(n^2)$
Melhor caso	$O(n)$