Ordenação por bolha
Percorre a lista várias vezes e troca os vizinhos que estão pela ordem errada. No fim de cada passagem, o maior valor que falta ordenar chega ao fim.
- melhor caso Ω(n)
- caso médio Θ(n²)
- pior caso O(n²)
- memória O(1)
- estável
- sem memória extra
O que significam estes termos?
- 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 demora cerca de quatro vezes mais; 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 quando se ordena por um só campo de um registo.
- Sem memória extra: ordena dentro da própria lista, sem uma segunda lista.
- a comparar
- a mover
- na posição final
Carregue em Reproduzir: as linhas mostram como o custo cresce
Carregue em Reproduzir ou avance passo a passo pelo algoritmo.
Espaço: reproduzir ou pausar. Setas esquerda e direita: avançar passo a passo. Home e End: saltar.
Experimente: Escolha uma lista quase ordenada. Depois de uma passagem sem trocas, o algoritmo para mais cedo.
Como funciona
Compara dois vizinhos de cada vez e troca-os se o da esquerda for maior. Assim, em cada passagem, o maior valor vai até à ponta direita, como uma bolha a subir. Se uma passagem não fizer nenhuma troca, a lista já está ordenada.
Quando é uma boa escolha
Quase nunca se usa em programas reais, porque é lento com listas longas. É ótimo para aprender: mostra a ideia base de ordenar comparando e trocando. Só é rápido quando a lista já está ordenada.