Este capítulo é um resumo de parte das seções 8.1-8.3 e 8.6 do livro do Sedgewick. Ele trata do seguinte
Problema: Rearranjar um vetor a[p..r] de modo que ele fique em ordem crescente.
Como já fizemos em outro capítulo, vamos supor que os elementos do vetor são de um tipo Item que admite comparação.
Começamos por tratar do problema auxiliar de intercalação (= to merge), que pode ser formulado assim:
Intercalar vetores crescentes a[0..N-1] e b[0..M-1] para produzir um vetor crescente c[0..N+M-1].
Vamos supor que os vetores são disjuntos no seguinte sentido: nenhuma parte da memória pertence, ao mesmo tempo, a dois dos três vetores envolvidos. O programa 8.1 do Sedgewick resolve assim o problema:
#define less(A, B) (A < B)
// A função recebe vetores disjuntos
// crescentes a[0..N-1] e b[0..M-1] e
// intercala os dois vetores produzindo o
// vetor crescente c[0..N+M-1].
//
void mergeAB (Item c[], Item a[],
int N, Item b[], int M) {
int i = 0, j = 0, k;
for (k = 0; k < N+M; k++) {
if (i == N) {
c[k] = b[j++];
continue;
}
if (j == M) {
c[k] = a[i++];
continue;
}
if (less(a[i], b[j])) c[k] = a[i++];
else c[k] = b[j++];
}
}
Eficiência: o algoritmo consome tempo proporcional ao número de elementos de c, ou seja, a N+M.
Suponha agora que queremos intercalar dois segmentos adjacentes de um vetor. O Programa 8.2 do livro do Sedgewick dá uma solução muito elegante e eficiente:
Item aux[maxN]; // A função recebe um vetor a[p..r] tal que os // subvetores a[p..q] e b[q+1..r] são // crescentes. Rearranja a[p..r] de modo que // ele fique crescente. (A função supõe que // p >= 0 e r < maxN.) // void merge (Item a[], int p, int q, int r) { int i, j, k; for (i = q+1; i > p; i--) aux[i-1] = a[i-1]; for (j = q; j < r; j++) aux[r+q-j] = a[j+1]; // agora i == p e j == r for (k = p; k <= r; k++) if (less(aux[j], aux[i])) a[k] = aux[j--]; else a[k] = aux[i++]; }
O vetor auxiliar aux é alocado estaticamente. Quem sabe seria melhor se a função merge alocasse aux dinamicamente.
Eis como o programa 8.3 de Sedgewick implementa o algoritmo Mergesort, que rearranja um vetor a[p..r] de modo que ele fique em ordem crescente:
// A função rearranja o vetor a[p..r] em
// ordem crescente.
//
void mergesort (Item a[], int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergesort (a, p, q);
mergesort (a, q+1, r);
merge (a, p, q, r);
}
}
Compare com o Quicksort: lá o trabalho pesado (partição) é feito antes de ordenar os dois subproblemas. No Mergesort, o trabalho pesado (intercalação) é feito depois que os subvetores estão ordenados.
Quantas comparações a função mergesort executa entre elementos do vetor? Resposta:
N lg N,
sendo N = r-p+1 o número de elementos do vetor. A prova é a mesma do caso mais favorável do Quicksort. Segue daí que o consumo de tempo do Mergesort é proporcional a N lg N.
void mergesort1 (Item a[], int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergesort1(a, p, q);
mergesort1(a, q+1, r);
merge(a, p, q+1, r);
}
}
void mergesort2 (Item a[], int p, int r) {
if (p <= r) {
int q = (p + r) / 2;
mergesort2(a, p, q);
mergesort2(a, q+1, r);
merge(a, p, q, r);
}
}
void mergesort3 (Item a[], int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergesort3(a, p, q-1);
mergesort3(a, q, r);
merge(a, p, q-1, r);
}
}
Tente mais uma versão, agora com (p+r+1)/2 no lugar de (p+r)/2.
O programa 8.5 de Sedgewick é uma versão iterativa do Mergesort.
Sedgewick chama essa versão de bottom-up Mergesort
,
ou seja, Mergesort de-baixo-para-cima
.
Ele chama a versão recursiva de top-down Mergesort
.
#define min(A, B) (A < B) ? A : B
// Esta função rearranja o vetor a[p..r] em
// ordem crescente.
//
void mergesortBU (Item a[], int p, int r) {
int i, m;
for (m = 1; m <= r-p; m = m+m)
for (i = p; i <= r-m; i += m+m)
merge (a, i, i+m-1, min(i+m+m-1, r));
}
Qual a invariante do processo iterativo externo?
O programa 8.6 de Sedgewick intercala duas listas encadeadas crescentes. Uma lista é crescente se x->item ≤ x->next->item para cada nó x da lista.
typedef struct node *link;
struct node {
Item item;
link next;
};
// Esta função recebe duas listas crescentes // a e b e devolve uma lista crescente que é // o resultado da intercalação das duas // listas dadas. // link list_merge (link a, link b) { struct node head; link c = &head; while (a != NULL && b != NULL) // c é o último nó da lista // cuja cabeça é head if (less(a->item, b->item)) { c->next = a; c = a; a = a->next; } else { c->next = b; c = b; b = b->next; } c->next = (a == NULL) ? b : a; return head.next; }
Ao contrário da versão vetorial, a função list_merge não aloca espaço auxiliar: ela apenas rearranja os ponteiros next.
A função list_merge é usada na seguinte implementação do Mergesort para listas encadeadas, que copiei do programa 8.8 de Sedgewick:
// Esta função recebe uma lista encadeada c
// e rearanja a lista em ordem crescente.
// Ela devolve o endereço da lista
// rearranjada.
//
link list_mergesort (link c) {
link a, b;
if (c == NULL || c->next == NULL) return c;
a = c;
b = c->next;
while (b != NULL && b->next != NULL) {
c = c->next;
b = b->next->next;
}
b = c->next;
c->next = NULL;
return list_merge (list_mergesort(a),
list_mergesort(b));
}
c == NULLna linha 3 do list_mergesort. Que diferença isso faz?