Heapsort
Organiza a lista num heap, uma árvore em que cada pai é maior do que os filhos. Depois leva o maior valor para o fim, uma e outra vez.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(1)
- não
- 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 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 invertida. Construir o heap quase não exige trocas; depois, cada ronda leva o maior valor para o fim.
Como funciona
O heap fica guardado na própria lista: o valor na posição i tem os filhos nas posições 2i+1 e 2i+2, e o maior valor está sempre à frente. Esse valor é trocado para o fim, o heap fica uma posição mais pequeno e é reparado. A parte ordenada cresce a partir da direita.
Quando é uma boa escolha
Quando é preciso rapidez que se mantenha boa mesmo no pior caso e sem memória extra, por exemplo em dispositivos pequenos. Em média é mais lento do que o quicksort, por isso é muitas vezes usado como plano B.