• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

iptleic

AJUDA

2 mensagens neste tópico

Komo funciona o heap sort?podem-me explicar assim por alto?e o fixdown?i o fixup?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O algoritmo heapsort é um algoritmo de ordenação generalista, e faz parte da família de algoritmos de ordenação por selecção.

Tem um desempenho em tempo de execução muito bom em conjuntos ordenados aleatoriamente, tem um uso de memória bem comportado e o seu desempenho em pior cenário é praticamente igual ao desempenho em cenário médio. Alguns algoritmos de ordenação rápidos têm desempenhos espectacularmente ruins no pior cenário, quer em tempo de execução, quer no uso da memória. O Heapsort trabalha no lugar e o tempo de execução em pior cenário para ordenar n elementos é de O (n log n). Para valores de n, razoavelmente grande, o termo log n é quase constante, de modo que o tempo de ordenação é quase linear com o número de itens a ordenar.

heapsort(tipo a[], int n)
{
   int i = n/2, pai, filho;
   tipo t;

   for (;
   {
      if (i > 0)
      {
          i--;
          t = a[i];
      }
      else
      {
          n--;
          if (n == 0)
             return;
          t = a[n];
          a[n] = a[0];
      }
     
      pai = i;
      filho = i*2 + 1;

      while (filho < n)
      {
          if ((filho + 1 < n)  &&  (a[filho + 1] > a[filho]))
              filho++;
          if (a[filho] > t)
          {
             a[pai] = a[filho];
             pai = filho;
             filho = pai*2 + 1;
          }
          else
             break;
      }
      a[pai] = t;
   }
}

Quanto ao restante dá uma olhada AQUI

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora