Este é o meu algorítmo preferido, apesar de ser pouco utilizado. O seu ponto chave é que tanto o tempo médio como o pior caso são proporcionais a N log(N).
Na prática, o tempo do HeapSort varia muito pouco com os dados sendo ordenados. Isto significa que se ele for rápido suficiente com um amostra de tamanho N, ele será rápido quaisquer que forem os dados de tamanho N que você jogar nele,
A idéia por trás do HeapSort é a mesma do torcedor do time eliminado num torneio "mata-mata". Olhando na figura abaixo, é claro que o time Amarelo é o campeão, mas quem é o segundo melhor? Não é preciso fazer um novo torneio completo, os candidatos são somente quem perdeu para o campeão (Marrom, Azul e Verde). O truque no HeapSort é usar uma estrutura de árvore para "lembrar" o resultado das comparações anteriores.
No HeapSort uma estrutura de árvore binária é obtida sem utilizar memória adicional guardando os dados de forma que- o pai da chave no índice k está no índice k/2
- os filhos da chave no índice k estão nos índices 2*k e 2*k+1
O HeapSort tem dois passos. No primeiro, transformamos os dados de entrada em um heap. Isto é feito partindo do topo e descendo a árvore movendo para cima os filhos que forem maiores que os seus pais. No final do primeiro passo, a primeira posição contém a maior chave. Entramos então no segundo passo, onde trocamos a primeira chave com a que está na última posição (colocando-a assim na sua posição final) e ajeitamos o heap para que a primeira posição contenha a maior chave das restantes. Este procedimento é repetido até que todas as chaves estejam na sua posição final.O HeapSort não é particularmente rápido para N pequeno, mas para N grande é muito bom. O QuickSort é mais rápido na maioria das vezes, mas existe sempre o pior caso espreitando na esquina.
O HeapSort não requer memória adicional e não é estável.
Na próxima parte: o primeiro exemplo.
2 comentários:
excelente explicação!
uso com frequencia o heap sort e ele é certamente o meu favorito. é simples, elegante e rapido.
implementei em umas 20 linhas...e olha que fiz usando várias indireções, usando vetores de indices, etc.
eu nunca entendi como funciona o quicksort direito =-P
O QuickSort certamente é melhor do que o heap, usa ordenação recursiva em particionamentos. O algoritmo marca um pivo no centro do vetor, coloca todos numeros maiores que o pivo, a direita dele, e todos numeros menores que o pivo a esquerda dele, aí então, mantém o pivo, do centro, porque este já está no seu lugar do vetor, e faz usando recursividade o mesmo procedimento com os novos pivores criados, que seriam os elementos centrais das novas partições que são os elementos da direita e os da esquerda do pivo inicial. Espero ter ajudado.
Este link, mostra uma animação muito boa, do QuickSort:
http://diuf.unifr.ch/people/bertinie/visuale/2007/02/a_quicksort_animation.html
grande abraço.
Postar um comentário