Depende do que vc quer dizer com "complexidade", vou tentar demonstrar através da notação Big O
. Bubble sort consiste em percorrer uma lista e ir trocando as posições dos elementos com o objetivo de deixar a lista ordenada, ou seja, de qualquer forma será necessario percorrer a lista inteira, pelo menos uma vez.
Melhor caso:
Se a lista já estiver ordenada então não será feita nenhuma troca (swap), ai teriamos o melhor caso, onde teriamos que comparar os valores na posição 0, posição 1, 2, ..., n-2, até n-1, como todos os valores em suas posições são menores do que seu vizinho sucessor, não haveria nenhuma troca, e fariamos apenas um loop sobre a lista, então em uma lista de n
elementos teriamos um total de n-1
, comparações, para a notação Big O, desconsideramos o termo -1, então teremos, para o melhor caso: O(n).
Pior caso:
Bubblesort tem o seu pior caso quando a lista está em ordem reversa, nesse caso, no loop inicial o item que estava no posição 0 terminará na posição n-1, vejamos um exemplo:
lista = [5, 4, 3, 2, 1]
^
Posição 0
# Loop inicial
4, 5, 3, 2, 1
4, 3, 5, 2, 1
3, 4, 5, 2, 1
3, 4, 2, 5, 1
3, 4, 2, 1, 5
^
Posição n-1
O próximo loop moverá o segundo maior valor da lista para a posição n-2 da lista.
lista_atualizada = [3, 4, 2, 1, 5]
# Segundo loop
3, 2, 4, 1, 5
3, 2, 1, 4, 5
^ Posição n-2
Após n-1 loops a lista estará ordenada e o algoritmo ainda fará mais um loop antes do return
, o numero de comparacoes será n(n-1)
ou n²-n
, para a notação Big O, removemos os coeficientes constantes e os termos não dominantes, e teremos: O(n²)