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 o problema que consomem tempo proporcional a n2. Vamos examinar agora um algoritmo mais complexo mas mais rápido.
Veja o verbete Merge sort na Wikipedia.
Antes de resolver nosso problema principal é preciso resolver o seguinte problema auxiliar: dados vetores crescentes v[p .. q-1] e v[q .. r-1], rearranjar v[p .. r-1] em ordem crescente. Basta tratar do caso em que os vetores v[p .. q-1] e v[q .. r-1] não são vazios.
p | q-1 | q | r-1 | |||||||
111 | 333 | 555 | 555 | 777 | 999 | 999 | 222 | 444 | 777 | 888 |
É 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 caráter ordenado das duas "metades". Mas isso é muito lento; precisamos de um algoritmo mais rápido.
O problema é fácil, mas não é trivial. Será preciso usar um vetor auxiliar, digamos w, do mesmo tipo e mesmo tamanho que 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.
void
intercala1 (int p, int q, int r, int v[])
{
int i, j, k, *w;
w = mallocX ((r-p) * sizeof (int));
i = p; j = q;
k = 0;
while (i < q && j < r) {
if (v[i] <= v[j]) w[k++] = v[i++];
else w[k++] = v[j++];
}
while (i < q) w[k++] = v[i++];
while (j < r) w[k++] = v[j++];
for (i = p; i < r; ++i) v[i] = w[i-p];
free (w);
}
O tempo que a função consome para fazer o serviço é proporcional ao número de comparações entre elementos do vetor. Esse número é no máximo r - p - 1 . O consumo de tempo também é proporcional ao número de movimentações, ou seja, cópias de elementos do vetor de um lugar para outro. Esse número é igual a 2(r-p). Resumindo, o consumo de tempo da função é proporcional ao número de elementos do vetor, ou seja,
proporcional a r - p .
i = p; j = q; k = 0; while (i < q && j < r) { if (v[i] <= v[j]) w[k++] = v[i++]; else w[k++] = v[j++]; } while (i < q) w[k++] = v[i++]; while (j < r) w[k++] = v[j++]; for (i = p; i < r; ++i) v[i] = w[i-p];
i = p; j = q; k = 0; while (i < q && j < r) { if (v[i] <= v[j]) w[k++] = v[i++]; else w[k++] = v[j++]; } while (i < q) w[k++] = v[i++]; for (i = p; i < j; ++i) v[i] = w[i-p];
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++]; } for (i = p; i < r; ++i) v[i] = w[i-p];
i = p; j = q; k = 0; 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++]; } for (i = p; i < r; ++i) v[i] = w[i-p];
int w[MAX], i, j, k; for (i = p; i < q; i++) w[i] = v[i]; for (j = q; j < r; j++) w[r+q-j-1] = v[j]; i = p; j = r-1; for (k = p; k < r; k++) if (w[i] < w[j])) v[k] = w[i++]; else v[k] = w[j--];
Sedgewick tem uma maneira mais elegante de escrever o algoritmo de intercalação. O primeiro for copia v[p..q-1] para w[0..q-p-1]; o segundo, copia v[q..r-1] para w[q-p..r-p-1] em ordem invertida. Com isso, a intercalação de w[0..q-p-1] com w[q-p..r-p-1] pode ser feita em um único for.
// A função recebe vetores crescentes v[p..q-1] e
// v[q..r-1] e rearranja v[p..r-1] em ordem crescente.
void
intercala2 (int p, int q, int r, int v[])
{
int i, j, k, *w;
w = mallocX ((r-p) * sizeof (int));
for (i = 0, k = p; k < q; i++, k++) w[i] = v[k];
for (j = r-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--];
free (w);
}
Tal como a versão anterior, esta consome tempo proporcional a r - p.
Agora podemos usar qualquer das funções intercala discutidas acima para escrever um algoritmo rápido de ordenação: o algoritmo recebe um vetor v[p..r-1] e rearranja o vetor em ordem crescente. O algoritmo é recursivo. A base da recursão é o caso p ≥ r-1; nesse caso 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) {
int q = (p + r)/2;
mergesort (p, q, v);
mergesort (q, r, v);
intercala (p, q, r, v);
}
}
O resultado da divisão por 2 na expressão (p+r)/2 é automaticamente truncado. Por exemplo, (3+6)/2 vale 4. Para rearranjar v[0..n-1] em ordem crescente basta executar mergesort (0, n, v).
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
111 | 999 | 222 | 999 | 333 | 888 | 444 | 777 | 555 | 666 | 555 |
111 | 999 | 222 | 999 | 333 | 888 | 444 | 777 | 555 | 666 | 555 |
111 | 999 | 222 | 999 | 333 | 888 | 444 | 777 | 555 | 666 | 555 |
111 | 999 | 222 | 999 | 333 | 888 | 444 | 777 | 555 | 666 | 555 |
111 | 999 | 222 | 999 | 333 | 888 | 444 | 777 | 555 | 666 | 555 |
Quanto tempo o algoritmo consome para ordenar v[0..n-1]? Como o número de elementos do vetor é reduzido à metade em cada chamada do mergesort, o número total de "rodadas" é log2n. Na primeira rodada, nosso problema original é reduzido a dois outros: ordenar v[0 .. n/2-1] e ordenar v[n/2 .. n-1]. Na segunda rodada temos quatro problemas: ordenar 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. O tempo total que intercala gasta em cada "rodada" é n (por que? pense!). Conclusão: mergesort consome tempo proporcional a
n log2n .
Isso é bem melhor que o tempo n2 gasto pelos algoritmos da página anterior. Por exemplo, se a ordenação de n números exige t segundos, a ordenação de 16n números exigirá apenas 64t segundos (contra os 256t segundos do algoritmo anterior.)
Observação final: Como mergesort é mais complexo que os algoritmos da página anterior, ele só é realmente mais rápido na prática quando n é grande.
Veja algumas animações do algoritmo Mergesort:
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); } }
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); } }
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); } }
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); } }
void mergesort5 (int p, int r, int v[]) { if (p < r-1) { q = r - 1; mergesort5 (p, q, v); intercala (p, q, r, v); }
A versão iterativa do algoritmo Mergesort recebe um vetor v[0..n-1] e rearranja o vetor em ordem crescente. A idéia é 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 1, 2, 4, . . . .
// 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 b == 2.
0 | p | p+b | p+2*b | n-1 | ||||||
111 | 999 | 222 | 999 | 333 | 888 | 444 | 777 | 555 | 666 | 555 |
1 2 3 , 0 2 4 6 e 4 5 6 7 8 9 .
Explore esta idéia.