Ordenação por bolha
Percorre a lista várias vezes e troca os vizinhos que estão na ordem errada. Ao fim de cada passagem, o maior valor que falta ordenar chega ao final.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- sim
- sim
Melhor caso: como o tempo cresce com o tamanho n da lista quando a entrada é a mais fácil para este algoritmo.
Caso médio: como o tempo costuma crescer com n. Com n², o dobro de valores leva cerca de quatro vezes mais tempo; n log n cresce bem menos.
Pior caso: o crescimento com a entrada mais difícil. Útil quando a velocidade nunca pode cair.
Memória: quanta memória extra é necessária além da lista. 1 significa algumas variáveis; n, uma cópia da lista.
Estável: dois valores iguais mantêm a ordem original. Importa ao ordenar por um só campo de um registro.
Sem memória extra: ordena dentro da própria lista, sem uma segunda lista.
- comparando
- movendo
- na posição final
Experimente: Escolha uma lista quase ordenada. Depois de uma passagem sem trocas, o algoritmo para mais cedo.
Como funciona
Compara dois vizinhos por vez e troca os dois se o da esquerda for maior. Assim, em cada passagem, o maior valor vai até a ponta direita, como uma bolha subindo. Se uma passagem não fizer nenhuma troca, a lista já está ordenada.
Quando é uma boa escolha
Quase nunca é usado em programas reais, porque é lento em listas longas. É ótimo para aprender: mostra a ideia básica de ordenar comparando e trocando. Só é rápido quando a lista já está ordenada.