Projeto de Algoritmos  |  Linguagem C  |  Índice  |  English

Mergesort: ordenação por intercalação

Considere o problema de ordenação discutido em outro capítulo:  rearranjar um vetor v[0 .. n-1] de tal modo que ele fique em ordem crescente, isto é, de tal modo que tenhamos v[0] ≤ . . . ≤ v[n-1].  O outro capítulo analisou alguns algoritmos simples para o problema. Aqueles algoritmos são quadráticos, ou seja, eles consomem uma quantidade de tempo proporcional a n².

O presente capítulo examina um algoritmo mais sofisticado e muito mais rápido que usa a estratégia da divisão-e-conquista. A ideia é simples: se a primeira metade do vetor já estiver em ordem crescente e a segunda metade também for crescente, então as duas metades podem ser rapidamente intercaladas de modo que o vetor todo fique em ordem crescente.

Intercalação de vetores ordenados

Antes de resolver nosso problema principal é preciso resolver o seguinte problema da intercalação (= merge):  dados vetores crescentes v[p .. q-1] e v[q .. r-1], rearranjar v[p .. r-1] em ordem crescente.

Seria fácil resolver o problema da intercalação em tempo proporcional ao quadrado do tamanho do vetor v[p..r-1]:  bastaria ignorar que as duas metades já estão ordenadas e usar um dos algoritmos básicos de ordenação.  Mas é possível fazer algo bem mais rápido.  Para isso, será preciso usar uma área de trabalho, digamos  w[0..r-p-1],  do mesmo tipo e mesmo tamanho que o vetor v[p..r-1].

// A função recebe vetores crescentes v[p..q-1] 
// e v[q..r-1] e rearranja v[p..r-1] em ordem 
// crescente.

static void 
intercala (int p, int q, int r, int v[]) 
{
   int *w;  // 1
   w = malloc ((r-p) * sizeof (int));  // 2
   int i = p, j = q;  // 3
   int k = 0;  // 4

   while (i < q && j < r) {  // 5
      if (v[i] <= v[j])  w[k++] = v[i++];  // 6
      else  w[k++] = v[j++];  // 7
   }  // 8
   while (i < q)  w[k++] = v[i++];  // 9
   while (j < r)  w[k++] = v[j++];  // 10
   for (i = p; i < r; ++i)  v[i] = w[i-p];  // 11
   free (w);  // 12
}

A palavra-chave static indica que a função intercala tem caráter auxiliar, e não deve ser invocada diretamente pelo usuário do algoritmo de ordenação.

Desempenho.  A função intercala consiste essencialmente em movimentar elementos do vetor v de um lugar para outro (primeiro de v para w e depois de w para v).  A função executa

2n

dessas movimentações, sendo n o tamanho do vetor v[p..r-1].  O tempo que intercala consome é proporcional ao número de movimentações.  Portanto, o consumo de tempo da função é proporcional a n.  Assim, o algoritmo é linear.

Exercícios 1

Intercalação com sentinelas

Sedgewick escreve o algoritmo de intercalação de uma maneira mais interessante.  Primeiro, copia o vetor v[p..q-1] para o espaço de trabalho w[0..q-p-1];  depois, copia v[q..r-1] para o espaço w[q-p..r-p-1] em ordem inversa.  Com isso, a metade esquerda de w serve de sentinela para a metade direita, e vice-versa, durante o processo de intercalação.  Assim, não há necessidade de verificar, a cada iteração, as condições de fronteira  i < q-p  e  j ≥ q-p.

// Esta função recebe vetores crescentes 
// v[p..q-1] e v[q..r-1] e rearranja
// v[p..r-1] em ordem crescente.

static void
s_intercala (int p, int q, int r, int v[])
{
   int i, j, *w;
   w = malloc ((r-p) * sizeof (int));

   for (i = p; i < q; ++i) w[i-p] = v[i];
   for (j = q; j < r; ++j) w[r-p+q-j-1] = v[j];
   i = 0; j = r-p-1;
   for (int k = p; k < r; ++k)
      if (w[i] <= w[j]) v[k] = w[i++];
      else v[k] = w[j--];
   free (w);
}

Tal como a versão anterior, esta consome tempo proporcional ao tamanho do vetor v[p..r-1].

Exercícios 2

Algoritmo Mergesort

O algoritmo Mergesort usa a estratégia da divisão-e-conquista para ordenar o vetor dado. A fase da divisão é simples: basta quebrar o vetor em dois. A fase da conquista foi implementada acima pela função intercala.

A função recursiva abaixo rearranja o vetor v[p..r-1] em ordem crescente. A base da recursão é formada pelas instâncias em que p ≥ r-1 ; nessas instâncias, o vetor tem no máximo 1 elemento e portanto não é preciso fazer nada para deixar o vetor fique em ordem crescente.

// A função mergesort rearranja o vetor 
// v[p..r-1] em ordem crescente.

void
mergesort (int p, int r, int v[])
{
   if (p < r-1) {                 // 1
      int q = (p + r)/2;          // 2
      mergesort (p, q, v);        // 3
      mergesort (q, r, v);        // 4
      intercala (p, q, r, v);     // 5
   }
}

(Notas: 1. Você pode trocar intercala por s_intercala na linha 5 pois essas duas funções são equivalentes. 2. O resultado da divisão por 2 na expressão (p+r)/2 é automaticamente truncado. Por exemplo, (3+6)/2 vale 4.)

Se p < r-1, a instância v[p..r-1] do problema é reduzida ao par de instâncias v[p..q-1] e v[q..r-1]. Essas duas instâncias são estritamente menores que a instância original, uma vez que q < r e q > p (confira!) no fim da linha 2. Assim, por hipótese de indução, o vetor v[p..q-1] estará em ordem crescente no fim da linha 3 e o vetor v[q..r-1] estará em ordem crescente no fim da linha 4. Portanto, no fim da linha 5, o vetor v[p..r-1] estará em ordem crescente, graças à operação de intercalação.

Para rearranjar em ordem crescente um vetor v[0..n-1], como quer a formulação original do problema, basta executar mergesort (0, n, v).

Exercícios 3

Animações do Mergesort

A animação à direita (copiada da Wikipedia) mostra a ordenação de um vetor v[0..99] que contém uma permutação aleatória de 0..99. (Veja uma versão mais lenta da animação.) Cada elemento v[i] é representado pelo ponto de coordenadas (i, v[i]).

Há muitas outras animações do Mergesort na rede WWW. Veja algumas:

• Comparison Sorting Algorithms, de David Galles (University of San Francisco).
• Sorting Algorithms Animations.
• animação 15 sorting algorithms in 6 minutes, de Timo Bingmann, no YouTube.
• Merge-sort com dança folclórica da Transilvânia, Universidade Sapientia (Romênia).

Exercícios 4

Desempenho do algoritmo Mergesort

Aplique a função mergesort a um vetor v[0..n-1].  O tamanho do vetor é reduzido à metade a cada passo da recursão. Na primeira rodada, a instância original do problema é reduzida a duas menores:  v[0..n/2-1]  e  v[n/2..n-1].  Na segunda rodada, temos quatro instâncias:

v[0..n/4-1],  v[n/4..n/2-1],  v[n/2..3n/4-1]  e  v[3n/4..n-1].

E assim por diante, até que, na última rodada, cada instância tem no máximo 1 elemento.  O número total de rodadas é aproximadamente  log n  (portanto também aproximadamente lg(n)).

Em cada rodada, a função intercala executa  2n  movimentações de elementos do vetor v[0..n-1].  Assim, o número total de movimentações para ordenar v[0..n-1] é aproximadamente

2n log n .

É fácil constatar que o consumo de tempo da função mergesort é proporcional ao número total de movimentações, e portanto proporcional a

n log n .

Diz-se que o algoritmo é linearítmico.  O número n log n cresce muito mais devagar que n² e apenas um pouco mais rapidamente que n.  Assim, se um vetor de tamanho N exige T unidades de tempo, um vetor de tamanho 2N exigirá menos que 2.2 T unidades de tempo, desde que N seja maior que 2¹⁰. Da mesma forma, um vetor de tamanho 4N exigirá menos que 4.4 T unidades de tempo, desde que N seja maior que 2²⁰.  (Confira as contas!)

O consumo de tempo do Mergesort é proporcional a n log n enquanto o dos algoritmos elementares é proporcional a n².  Mas o fator de proporcionalidade é maior para o Mergesort, pois o código é mais complexo.  Assim, o Mergesort só se torna realmente mais rápido que os algoritmos elementares quando n é suficientemente grande.

Exercícios 5

Versão iterativa do Mergesort

A versão iterativa do algoritmo Mergesort rearranja um vetor v[0..n-1] em ordem crescente. A cada iteração, o algoritmo intercala dois blocos consecutivos de  b  elementos cada: o primeiro bloco com o segundo, o terceiro com o quarto, etc.  A variável b assume os valores 1, 2, 4, 8, . . .

// Esta função rearranja o vetor
// v[0..n-1] em ordem crescente.

void
mergesort_i (int n, int v[])
{
   int b = 1;
   while (b < n) {
      int p = 0;
      while (p + b < n) {
         int r = p + 2*b;
         if (r > n) r = n;
         intercala (p, p+b, r, v);
         p = p + 2*b; 
      }
      b = 2*b;
   }
}

A figura ilustra a iteração em que b vale 2:

Há muitas animações e visualizações interessantes da versão iterative do Mergesort:

• Animação do Mergesort produzida por Mike Bostock. [Dica de Yoshiharu Kohayakawa.] O vetor é representado por uma vassoura. Cada cerda da vassoura é um elemento do vetor e a inclinação da cerda é o valor do elemento.  Seguem algumas apresentações autônomas da animação:
  • Mergesort I. (Veja o código.)
  • Mergesort II. Os segmentos que estão sendo ordenados ficam em destaque. (Veja o código.)
  • Mergesort III. Uma visualização estática. (Veja o código.)
• Mergesort IV, por Mike Bostock. Uma animação/visualização com fitas coloridas que se entrelaçam. Recarregue para variar os dados. (Veja o código.)

Exercícios 6

Exercícios 7