Patrocínio Natura

Poderoso Algoritmo de Ordenação do Fundão da Computação

16 de abril de 2009

O Merge Sort é um algoritmo de ordenação para reordenar listas (ou qualquer outra estrutura de dado que possa ser acessada apenas sequencialmente, por exemplo arquivos) em uma ordem específica. Um bom exemplo do paradigma algorítmico da divisão e conquista.

Conceitualmente, o merge sort funciona da seguinte forma: Se a lista a ser ordenada é maior do que um item:

  1. Divide a lista não ordenada em duas sublistas de aproximadametne metade do tamanho
  2. Ordena cada uma das duas sublistas
  3. Junta as duas sublistas ordenas em uma única lista ordenada.

O merge sorte tem uma média e a performance no pior caso de O(n log(n)). Isto significa que ele geralmente precisa fazer menos comparações do que o quicksort. Contudo, o custo do algoritmo é um pouco superior ao do quicksort, e, dependendo da estrutura de dados a ser ordenada, pode consumir mais memória (embora isto tenha sido levado cada vez menos consideração). Ele também é muito mais eficiente do que o quicksort se os dados a serem ordenados puderem ser acessados eficientemente sequencialmente, o que o torna bastante popular em linguagens tais como LISP onde estruturas de dados acessadas sequencialmente são muito comuns. Merge sort é um algoritmo estável (ele não altera a ordem relativa de elementos que tem valores iguais).

list sort( n )
int n;
{
   list fi, la, temp;
   extern list r;
   if ( r == NULL ) 
        return( NULL );
   else if ( n>1 )
        return( merge( sort( n/2 ), sort( (n+1)/2 )));
   else     
   {
        fi = r; la = r;
        /*** Build list as long as possible ***/
        for ( r=r->next; r!=NULL; )
             if ( r->k >= la->k ) 
             {
                  la->next = r;
                  la = r;
                  r = r->next;
             }
             else if ( r->k <= fi->k ) 
             {
                  temp = r;
                  r = r->next;
                  temp->next = fi;
                  fi = temp;
             }
             else 
                  break;
        la->next = NULL;
        return( fi );
   }
};

Compatilhe esse artigo!

Nenhum Comentário

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

This site uses Akismet to reduce spam. Learn how your comment data is processed.