O algoritmo para classificação por bolhas requer um par de loops aninhados. O loop externo deve iterar uma vez para cada elemento no conjunto de dados (de tamanho n) enquanto o loop interno itera n vezes na primeira vez em que é inserido, n-1 vezes no segundo e assim por diante. Considere o propósito de cada loop. Conforme explicado acima, a classificação por bolha é estruturada de forma que, em cada passagem pela lista, o próximo maior elemento dos dados seja movido para seu lugar apropriado. Portanto, para obter todos os n elementos em seus lugares corretos, o loop externo deve ser executado n vezes.
O loop interno é executado em cada iteração do loop externo. Seu objetivo é colocar o próximo maior elemento que está sendo colocado no lugar. O loop interno, portanto, faz a comparação e troca de elementos adjacentes. Para determinar a complexidade desse loop, calculamos o número de comparações que devem ser feitas. Na primeira iteração do loop externo, ao tentar colocar o maior elemento, deve haver n – 1 comparações: a primeira comparação é feita entre o primeiro e o segundo elementos, a segunda é feita entre o segundo e o terceiro elementos, e assim por diante até que a n-1ª comparação seja feita entre o n-1º e o enésimo elemento. Na segunda iteração do loop externo, não há necessidade de comparar o com o último elemento da lista, porque ele foi colocado no local correto na passagem anterior. Portanto, a segunda iteração requer apenas n-2 comparações. Esse padrão continua até a penúltima iteração do loop externo, quando apenas os dois primeiros elementos da lista não são classificados; claramente, neste caso, apenas uma comparação é necessária. O número total de comparações, portanto, é (n – 1) + (n – 2) … (2) + (1) = n (n – 1) / 2 ou O (n2).
O melhor caso para classificação por bolha ocorre quando a lista já está classificada ou quase classificada. No caso em que a lista já está classificada, a classificação por bolha será encerrada após a primeira iteração, uma vez que nenhuma troca foi feita. Sempre que uma passagem é feita pela lista e nenhuma troca foi feita, é certo que a lista está ordenada. A classificação por bolha também é eficiente quando um elemento aleatório precisa ser classificado em uma lista classificada, desde que o novo elemento seja colocado no início e não no final. Quando colocado no início, ele simplesmente borbulhará no lugar correto e a segunda iteração na lista gerará 0 trocas, encerrando a classificação. Lembre-se de que se o elemento aleatório for colocado no final, a classificação por bolha perde sua eficiência porque cada elemento maior que ele deve borbulhar até o topo.
O pior caso absoluto para classificação por bolha é quando o o menor elemento da lista está na extremidade grande. Como em cada iteração apenas o maior elemento não classificado é colocado em seu local apropriado, quando o menor elemento está no final, ele terá que ser trocado a cada vez na lista e não irá para a frente da lista até que todos os n ocorreram iterações. Neste pior caso, são necessárias n iterações de n / 2 trocas para que a ordem seja, novamente, n2.
Melhor caso: nCaso médio: n2Sim caso: n2