4

Gostaria de saber como posso demonstrar por indução de cálculo a complexidade do algoritmo bubblesort, tanto no melhor caso, quanto no pior caso.

def bubble_Sort(alist):

    for numc in range(len(alist)-1,0,-1):

        for i in range(numc):

            if alist[i]>alist[i+1]:

                temp = alist[i]

                alist[i] = alist[i+1]

                alist[i+1] = temp



alist = [54,26,93,17,77,31,44,55,20]

bubble_Sort(alist)

print(alist)

1 Resposta 1

3

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²)

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .