Heap sort

Páginas: 2 (319 palavras) Publicado: 9 de novembro de 2011
O algoritmo heapsort
Não é difícil juntar tudo que dissemos acima para obter um algoritmo que coloque v[1..n] em ordem crescente.

// Rearranja os elementos do vetor v[1..n]
// demodo que fiquem em ordem crescente

void heapsort (int n, int v[])
{
int p, m, x;
for (p = n/2; p >= 1; --p)
peneira (p, n, v);
for (m = n; m >= 2; --m) {
x= v[1], v[1] = v[m], v[m] = x;
peneira (1, m-1, v);
}
}

O comando for transforma o vetor em um max-heap recorrendo cerca de n/2 vezes à função peneira. Feito isso, temosum processo iterativo controlado pelo segundo for. No início de cada iteração valem os seguinte invariantes:

o vetor v[1..n] é uma permutação do vetor original,
o vetor v[1..m] éum max-heap,

v[1..m] ≤ v[m+1..n] e

o vetor v[m+1..n] está em ordem crescente.
É claro que v[1..n] estará em ordem crescente quando m for igual a 1. 1 max-heap m crescente n888 777 666 555 444 333 222 111 000 999 999 999 999 999
elementos pequenos elementos grandes

Heapsort: desempenho
Quanto tempo o heapsort leva para fazer oserviço? O tempo é proporcional ao número de comparações entre elementos do vetor, e esse número não passa de

3 n log2n ,

mesmo no pior caso. De fato, o primeiro for constrói omax-heap inicial e faz no máximo n lg(n) comparações entre elementos do vetor. (Uma análise mais cuidadosa revela que o número de comparações não passa de n). O segundo for executa cercade n chamadas de peneira e cada uma dessas chamadas faz no máximo 2 lg(n) comparações entre elementos do vetor.

Heapsort: animações
Veja applets de animação do algoritmo:Sorting Algorithms Animation by David R. Martin
Sorting Algorithms na Universidade de British Columbia
Sorting Algorithms, página de Pat Morin na Universidade de Carlton, Canadá
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Heap sort
  • Merge Sort, Quick Sort e Heap Sort
  • Heap
  • sort
  • sort
  • Quick sort e shell sort
  • selection sort
  • Radix sort

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!