[Curso de AeED - Aula 04] [Algoritmo] Ordenação - Mergesort

Nosso problema:  Rearranjar um vetor v[0 .. n-1] de tal modo que ele fique em ordem crescente, ou seja, de tal modo que tenhamos v[0] ≤ . . . ≤ v[n-1].
Já analisamos alguns algoritmos simples para esse problema que consomem tempo quadrático, ou seja, tempo proporcional a n2.  Vamos examinar agora um algoritmo mais complexo mas bem mais rápido.

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.
p     q-1 q  r-1
111333555555777999999222444777888
É fácil resolver o problema em tempo proporcional ao quadrado de r-p:  basta ordenar o vetor v[p..r-1] sem dar atenção ao estado ordenado das duas metades. Mas é possível fazer algo bem melhor.  Para fazer 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 
intercala1 (int p, int q, int r, int v[]) 
{
   int i, j, k, *w;                        //  1
   w = mallocc ((r-p) * sizeof (int));     //  2
   i = p; j = q;                           //  3
   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 está aí apenas para indicar que a função intercala1 tem caráter auxiliar, e não deve ser invocada diretamente pelo usuário final do algoritmo de ordenação.)
Desempenho.   A função intercala1 consiste essencialmente em movimentar elementos do vetor v de um lugar para outro (primeiro de v para w e depois de wpara v).  A função executa
2n
dessas movimentações, sendo n o tamanho do vetor v[p..r-1].   O tempo que intercala1 consome é proporcional ao número de movimentações.  Portanto, o consumo de tempo da função é proporcional a n.

Exercícios 1

  1. Escreva uma função que receba vetores disjuntos x[0..m-1] e y[0..n-1], ambos em ordem crescente, e produza um vetor z[0..m+n-1] que contenha o resultado da intercalação dos dois vetores dados. Escreva duas versões da função: uma iterativa e uma recursiva.
  2. A função intercala1 está correta quando p é igual a q, ou seja, quando o vetor v[p..q-1] está vazio?  E quando o vetor v[q..r-1] está vazio?
  3. Troque as linhas 9 a 11 da função intercala1 pelas duas linhas a seguir. A função continua correta?
    while (i < q)  w[k++] = v[i++];
    for (i = p; i < j; ++i)  v[i] = w[i-p]; 
    
  4. Troque o bloco de linhas 5 a 8 da função intercala1 pelas linhas abaixo. Critique o efeito da troca.
    while (i < q && j < r) {
       if (v[i] <= v[j])  w[k++] = v[i++];
       if (v[i] > v[j])  w[k++] = v[j++]; }
    
  5. Na função intercala1, troque o bloco de linhas 3 a 10 pelas linhas abaixo. A função continua correta?
    i = p; j = q;
    for (k = 0; k < r-p; ++k) {
       if (j >= r || (i < q && v[i] <= v[j])) 
          w[k] = v[i++];
       else 
          w[k] = v[j++]; }
    
  6. Na função intercala1, troque o bloco de linhas 5 a 10 pelas linhas abaixo. A função continua correta?
    while (k < r-p) {
       while (i < q && v[i] <= v[j]) 
          w[k++] = v[i++];
       while (j < r && v[j] <= v[i]) 
          w[k++] = v[j++]; }
    
  7. Invariantes.  Quais são os invariantes do primeiro while na função intercala1?
  8. Critique a seguinte função de intercalação.  Ela insere cada elemento de v[q..r-1] em v[p..q-1] como o algoritmo de inserção. (Observe que a função faz a intercalação in loco, ou seja, sem usar vetor auxiliar.)
    int i;
    while (q < r) {
       int x = v[q];
       for (i = q-1; i >= p && v[i] > x; --i) 
          v[i+1] = v[i];
       v[i+1] = x;
       q++; }
    
  9. A seguinte solução do problema da intercalação está correta?  Quais os invariantes do while?  (Observe que a função faz a intercalação in loco, ou seja, sem usar vetor auxiliar.) Qual o consumo de tempo?
    int i, k, x;
    i = p; 
    while (i < q && q < r) {
       if (v[i] >= v[q]) {
          x = v[q];
          for (k = q - 1; k >= i; --k) 
             v[k+1] = v[k];
          v[i] = x;
          ++q; }
       ++i; }
    
  10. Desafio: intercalação in loco.  Invente um função de intercalação tão eficiente quanto intercala1 que resolva o problema in loco, ou seja, sem usar um vetor auxiliar.
  11. Um algoritmo de intercalação é estável se não altera a posição relativa de elementos iguais. A função intercala1 discutida acima é estável?  E se a comparação v[i] <= v[j]  for trocada por v[i] < v[j]?
  12. Intercalação de listas encadeadas.  Digamos (para efeito deste exercício) que uma lec é uma lista encadeada (sem cabeça) que contém uma sequência crescente de números inteiros. Escreva uma função que intercale duas lecs, produzindo assim uma terceira. Sua função não deve alocar novas células na memória, mas reaproveitar as células das duas listas dadas.
  13. União de listas encadeadas.  Digamos que uma lec é uma lista encadeada (sem cabeça) que contém uma sequência estritamente crescente de números inteiros.  (Portanto, uma lec representa um conjunto de números.)  Escreva uma função que faça a união de duas lecs.  A lista resultante deve ser uma lec e deve ser construída com as células das duas listas dadas.

Intercalação com sentinelas

Sedgewick tem uma maneira mais elegante de escrever o algoritmo de intercalação.  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 durante o processo de intercalação, e vice-versa.  Assim, a intercalação de w[0..q-p-1] com w[q-p..r-p-1] pode ser feita com base na comparação  w[i] <= w[j]  sem que seja preciso verificar, a cada iteração, as condições i < q-p e j ≥ q-p
// 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
intercala2 (int p, int q, int r, int v[])
{
   int i, j, k, *w;
   w = mallocc ((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 (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

  1. Discuta o seguinte código alternativo de intercala2:
    for (i = 0, k = p; k < q; ++i, ++k) 
       w[i] = v[k];
    for (j = r-p-1, k = q; k < r; --j, ++k) 
       w[j] = v[k];
    i = 0; j = r-p-1;
    for (k = p; k < r; ++k)
       if (w[i] <= w[j]) v[k] = w[i++];
       else v[k] = w[j--];
    
  2. [Sedgewick 8.6]  Mostre que a função intercala2 discutida acima não é estável.  Que modificações é preciso introduzir para que ela se torne estável?

Mergesort

Agora podemos usar qualquer das funções intercala discutidas acima para escrever um algoritmo de ordenação, um algoritmo rápido que rearranje qualquer vetor v[p..r-1] em ordem crescente.
O algoritmo é recursivo. A base da recursão é o caso p ≥ r-1; nesse caso, o vetor tem no máximo 1 elemento e portanto não é preciso fazer nada.
// 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
   }
}
(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, o código de mergesort reduz a instância v[p..r-1] do problema 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 p < q < r graças à condição p < r-1.  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, de acordo com a documentação da função intercala, o vetor v[p..r-1] estará em ordem crescente, como prometeu a documentação de mergesort.
012345678910
111999222999333888444777555666555
111999222999333888444777555666555
111999222999333888444777555666555
.
.
.
111999222333999444777888555555666
111222333999999444555555666777888
111222333444555555666777888999999
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

  1. Mostre que p < q < r no fim da linha 2 de mergesort.
  2. Que acontece se trocarmos (p+r)/2 por (p+r-1)/2 no código da função mergesort?  Que acontece se trocarmos (p+r)/2 por (p+r+1)/2?
  3. Submeta um vetor indexado por  1..4 à função mergesort. Teremos a seguinte sequência de invocações da função:
    mergesort (1,5,v)
        mergesort (1,3,v)
            mergesort (1,2,v)
            mergesort (2,3,v)
        mergesort (3,5,v)
            mergesort (3,4,v)
            mergesort (4,5,v)
    
    (observe a indentação).  Repita o exercício com um vetor  indexado por  1..5.
  4. Pegadinha.  Quais são os invariantes da função mergesort?
  5. A função mergesort é estável?
  6. Overflow.  Se o tamanho do vetor estiver próximo de INT_MAX, a execução da função mergesort pode descarrilar na linha  q = (p + r)/2;  em virtude de um overflowaritmético.  Como evitar isso?
  7. Testes com vetor aleatório.  Escreva um programa que teste, experimentalmente, a correção de sua implementação do algoritmo Mergesort. Use permutações aleatórias de 1..n para os testes. Compare o resultado da ordenação com 1..n.

Animações do Mergesort

Exercícios 4

  1. Esta função promete rearranjar v[p..r-1] em ordem crescente. A função está correta?
    void mergesort1 (int p, int r, int v[]) {
        if (p < r-1) {
           int q = (p + r) / 2;
           mergesort1 (p, q, v);  
           mergesort1 (q, r, v);
           intercala (p, q+1, r, v); } }
    
  2. Esta função promete rearranjar v[p..r-1] em ordem crescente. A função está correta?
    void mergesort2 (int p, int r, int v[]) {
        if (p < r) {
           int q = (p + r) / 2;
           mergesort2 (p, q, v);  
           mergesort2 (q, r, v);
           intercala (p, q, r, v); } }
    
  3. Esta função está correta? Ela promete rearranjar v[p..r-1] em ordem crescente.
    void mergesort3 (int p, int r, int v[]) {
        if (p < r-1) {
           int q = (p + r - 1) / 2;
           mergesort3 (p, q, v);  
           mergesort3 (q, r, v);
           intercala (p, q, r, v); } }
    
  4. Esta função rearranja v[p..r-1] em ordem crescente? E se trocarmos (p+r)/2 por (p+r+1)/2?
    void mergesort4 (int p, int r, int v[]) {
        if (p < r-1) {
           int q = (p + r) / 2;
           mergesort4 (p, q-1, v);  
           mergesort4 (q-1, r, v);
           intercala (p, q-1, r, v); } }
    
  5. Esta função rearranja v[p..r-1] em ordem crescente?
    void mergesort5 (int p, int r, int v[]) {
       if (p < r-1) {
          q = r - 2;
          mergesort5 (p, q, v);
          if (v[r-2] > v[r-1]) {
             int t = v[r-2]; v[r-2] = v[r-1]; v[r-1] = t; }
          intercala (p, q, r, v); } }
    
  6. Esta função rearranja v[p..r-1] em ordem crescente?
    void mergesort6 (int p, int r, int v[]) {
       if (p < r-1) {
          q = r - 1;
          mergesort6 (p, q, v);
          intercala (p, q, r, v); } }
    
  7. Suponha que sua biblioteca tem uma função  mrg (p, q, r, v)  que funciona assim: recebe um vetor v tal que  v[p..q] e v[q+1..r-1] são crescentes e rearranja o vetor de modo que v[p..r-1] fique crescente.   Use mrg para implementar o algoritmo Mergesort.
  8. Suponha que sua biblioteca tem uma função  interc (v, p, q, r)  que recebe um vetor v tal que v[p..q-1] está em ordem crescente e v[q..r-1] está em ordem crescente e rearranja o vetor de modo que v[p..r-1] fique em ordem crescente.  (Qual o menor valor de q que interc deve aceitar? Qual o maior valor?)  Use interc para escrever uma função mrgsrt (v, p, r) que rearranje um vetor v[p..r] em ordem crescente.

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.  (Veja a função lg no capítulo Documentação.) 
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 .
O número n log n cresce bem mais devagar que n2 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 210. Da mesma forma, um vetor de tamanho 4N exigirá menos que 4.4 T unidades de tempo, desde que N seja maior que 220.
O consumo de tempo da função mergesort, proporcional a n log n, é muito melhor que o dos algoritmos elementares, que consomem tempo proporcional a n2.  Entretanto, o fator de proporcionalidade é maior no caso do mergesort, pois o código é mais complexo.  Assim, mergesort só se torna realmente mais rápido quando n é suficientemente grande.

Exercícios 5

  1. Cronometragem.  Escreva um programa que cronometre sua implementação do Mergesort (use a função clock da biblioteca time).  Divida os tempos por n log n para comparar com as previsões teóricas.
  2. Versão truncada.  Escreva uma versão do algoritmo Mergesort com cutoff para vetores pequenos:  quando o vetor a ser ordenado tiver menos que M elementos, a ordenação passa a ser feita pelo algoritmo de inserção.  O valor de M pode ficar entre 10 e 20.   (Esse truque é usado na prática porque o algoritmo de inserção é mais rápido que o Mergesort puro quando o vetor é pequeno.)
  3. Alocação/desalocação excessivos.  A função mergesort acima chama as funções malloc e free muitas vezes (as chamadas acontecem dentro de intercala).  Escreva uma versão da função que contenha o código da função de intercalação e chame malloc uma só vez. 
  4. Desafio: Mergesort in loco.  Invente uma implementação de Mergesort que façam o serviço in loco, ou seja, dispensem o uso de um vetor auxiliar.
  5. Ordem decrescente.  Escreva uma versão recursiva do algoritmo Mergesort que rearranje um vetor v[p..r-1] em ordem decrescente.  Sua função deve conter o código da intercalação (que deve começar com v[p..q-1] e v[q..r-1] decrescentes e terminar com v[p..r-1] decrescente).
  6. A seguinte função recursiva pretende encontrar o valor de um elemento máximo do vetor v[p..r], não necessariamente ordenado. É claro que o problema só faz sentido se p ≤ r
    int max (int p, int r, int v[]) {
       if (p == r) return v[r];
       else {
          int q, x, y;
          q = (p + r)/2;
          x = max (p, q, v);
          y = max (q+1, r, v);
          if (x >= y) return x;
          else return y; } }
    
    A função está correta? Ela é mais rápida que a função iterativa óbvia? Quantas vezes a função chama a si mesma? Suponha que p e r valem 0 e 6 respectivamente e mostre a sequência, devidamente indentada, das chamadas de max.

Versão iterativa do Mergesort

A versão iterativa do algoritmo Mergesort recebe um vetor v[0..n-1] e rearranja o vetor em ordem crescente. A ideia é muito simples. A cada iteração, intercalamos dois blocos com  b  elementos cada: o primeiro bloco com o segundo, o terceiro com o quarto, etc.  A variável b assume os valores 1248, . . .
// Esta função rearranja o vetor v[0..n-1] 
// em ordem crescente.

void
mergesort_i (int n, int v[])
{
   int p, r;
   int b = 1;
   while (b < n) {
      p = 0;
      while (p + b < n) {
         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 == 2:
0   p p+b p+2b n-1
111999222999333888444777555666555

Animações da versão iterativa do Mergesort

Exercícios 6

  1. Invariantes.  Quais são os invariantes do while externo na função mergesort_i?  E os invariantes do while interno?
  2. Segmentos crescentes.  A função mergesort_i começa por quebrar o vetor original em segmentos de comprimento 1.  Por que não começar com segmentos crescentes maximais?  Exemplo: os segmentos crescentes maximais do vetor  1 2 3 0 2 4 6 4 5 6 7 8 9   são   1 2 3 ,  0 2 4 6  e  4 5 6 7 8 9 .  Explore esta ideia. 

Exercícios 7

  1. Listas encadeadas.  Escreva uma versão do algoritmo Mergesort que rearranje uma lista encadeada em ordem crescente.  Sua função não deve alocar novas células na memória.  Faça duas versões: uma recursiva e uma iterativa. 
  2. Número de inversões.  O número de inversões de um vetor v[0..n-1] é o número de pares ordenados (i,j) tais que  0 ≤ i < j < n  e  v[i] > v[j].  Escreva uma função que calcule o número de inversões de um vetor dado. O consumo de tempo de sua função deve ser proporcional a n log n no pior caso.
  3. Distância tau de Kendall.  Suponha dadas duas permutações, digamos x[0..n-1] e y[0..n-1], de um mesmo conjunto de números.  A distância tau entre x e y é o número de pares de elementos do conjunto que estão em ordem diferente em x e y, ou seja, a cardinalidade do conjunto X \ Y onde X é o conjunto de todos os pares (x[i],x[j]) tais que i < j e Y é o conjunto de todos os pares (y[i],y[j]) tais que i < j.  (A definição não é assimétrica pois os conjuntos X \ Y e X \ Y têm a mesma cardinalidade.)  Escreva uma função eficiente que calcule a distância tau entre x e y.
Atualizado em 2016-03-15
http://www.ime.usp.br/~pf/algoritmos/
Paulo Feofiloff
DCC-IME-USP
[Curso de AeED - Aula 04] [Algoritmo] Ordenação - Mergesort [Curso de AeED - Aula 04] [Algoritmo] Ordenação - Mergesort Reviewed by Vinicius dos Santos on 10:28:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!