O Merge Sort é um algoritmo clássico de ordenação baseado no paradigma “dividir para conquistar”. Em Prolog, sua implementação é particularmente elegante devido à natureza recursiva das listas e ao poder da unificação. Vamos construir o algoritmo passo a passo.
1. O Paradigma “Dividir para Conquistar”
O Merge Sort segue três passos fundamentais:
- Distribuir (Dividir): A lista original é dividida em duas sublistas aproximadamente iguais.
- Ordenar recursivamente (Conquistar): Cada sublista é ordenada recursivamente usando o mesmo algoritmo.
- Intercalar (Combinar): As duas sublistas ordenadas são mescladas em uma única lista ordenada.
2. Passo 1: Distribuir — distribui/3 (Programa 5.4)
O predicado distribui/3 divide uma lista em duas, alternando os elementos entre elas.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
% distribui(L, A, B) - A e B são as duas metades de L (alternadas) % Caso base: lista vazia → duas listas vazias distribui([], [], []). % Caso base: lista com um elemento → A recebe o elemento, B fica vazio distribui([X], [X], []). % Passo recursivo: [X,Y|Z] → X vai para A, Y vai para B, continua com Z distribui([X,Y|Z], [X|A], [Y|B]) :- distribui(Z, A, B). |
Explicação Passo-a-Passo
- distribui([], [], []): Se a lista está vazia, ambas as sublistas estão vazias.
- distribui([X], [X], []): Se a lista tem um elemento, ele vai para a primeira lista.
- distribui([X,Y|Z], [X|A], [Y|B]): O primeiro elemento X vai para A, o segundo Y vai para B, e a recursão distribui o restante Z.
Exemplo de Distribuição
|
1 2 3 4 5 6 7 |
?- distribui([1,2,3,4,5,6], A, B). A = [1,3,5], B = [2,4,6]. ?- distribui([a,b,c,d,e], A, B). A = [a,c,e], B = [b,d]. |
3. Passo 2: Intercalar — intercala/3
O predicado intercala/3 mescla duas listas ordenadas em uma única lista ordenada.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
% intercala(A, B, C) - C é a fusão ordenada de A e B % Caso base: A vazia → resultado é B intercala([], B, B). % Caso base: B vazia → resultado é A intercala(A, [], A). % Passo recursivo: compara as cabeças, coloca a menor primeiro intercala([X|A], [Y|B], [X|C]) :- X =< Y, intercala(A, [Y|B], C). intercala([X|A], [Y|B], [Y|C]) :- X > Y, intercala([X|A], B, C). |
Explicação Passo-a-Passo
- intercala([], B, B): Se A está vazia, o resultado é B.
- intercala(A, [], A): Se B está vazia, o resultado é A.
- intercala([X|A], [Y|B], [X|C]): Se X ≤ Y, X é colocado na frente e a intercalação continua com A e [Y|B].
- intercala([X|A], [Y|B], [Y|C]): Se X > Y, Y é colocado na frente e a intercalação continua com [X|A] e B.
Exemplo de Intercalação
|
1 2 3 4 5 |
?- intercala([1,3,5], [2,4,6], C). C = [1,2,3,4,5,6]. ?- intercala([a,c,e], [b,d], C). C = [a,b,c,d,e]. |
4. Passo 3: Ordenar — ordena/2
O predicado ordena/2 combina distribuição, ordenação recursiva e intercalação.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
% ordena(L, S) - S é a lista L ordenada % Caso base: lista vazia ordena([], []). % Caso base: lista com um elemento ordena([X], [X]). % Passo recursivo: divide, ordena cada parte, intercala ordena([X,Y|Z], S) :- distribui([X,Y|Z], A, B), % Divide a lista ordena(A, As), % Ordena a primeira metade ordena(B, Bs), % Ordena a segunda metade intercala(As, Bs, S). % Intercala as duas metades ordenadas |
5. Fluxo de Execução: ordena([3,5,0,4,1,2], S)
Vamos acompanhar a execução passo a passo:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
1. distribui([3,5,0,4,1,2], A, B) A = [3,0,1], B = [5,4,2] 2. ordena([3,0,1], As) a. distribui([3,0,1], A1, B1) → A1 = [3,1], B1 = [0] b. ordena([3,1], As1) - distribui([3,1], A2, B2) → A2 = [3], B2 = [1] - ordena([3], [3]) - ordena([1], [1]) - intercala([3], [1], S1) → S1 = [1,3] c. ordena([0], [0]) d. intercala([1,3], [0], As) → As = [0,1,3] 3. ordena([5,4,2], Bs) a. distribui([5,4,2], A3, B3) → A3 = [5,2], B3 = [4] b. ordena([5,2], Bs1) - distribui([5,2], A4, B4) → A4 = [5], B4 = [2] - ordena([5], [5]) - ordena([2], [2]) - intercala([5], [2], S2) → S2 = [2,5] c. ordena([4], [4]) d. intercala([2,5], [4], Bs) → Bs = [2,4,5] 4. intercala([0,1,3], [2,4,5], S) S = [0,1,2,3,4,5] |
Consulta Completa
|
1 2 3 4 5 6 7 8 9 10 11 |
?- ordena([3,5,0,4,1,2], S). S = [0,1,2,3,4,5]. ?- ordena([5,2,8,1,9,3], S). S = [1,2,3,5,8,9]. ?- ordena([], S). S = []. ?- ordena([7], S). S = [7]. |
6. Árvore de Recursão do Merge Sort
Visualize a árvore de recursão para ordena([3,5,0,4,1,2], S):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
[3,5,0,4,1,2] / \ [3,0,1] [5,4,2] / \ / \ [3,1] [0] [5,2] [4] / \ / \ [3] [1] [5] [2] | | | | [3] [1] [5] [2] \ / \ / [1,3] [2,5] \ / [0,1,3] [2,4,5] \ / [0,1,2,3,4,5] |
7. Análise de Complexidade
O Merge Sort tem complexidade:
- Tempo: O(n log n) no pior caso, médio e melhor caso.
- Espaço: O(n) para armazenar as sublistas durante a intercalação.
Em Prolog, a implementação é particularmente elegante porque:
- A recursão natural do Prolog se alinha perfeitamente com a estrutura do algoritmo.
- A unificação simplifica a distribuição e intercalação.
- O código é declarativo e fácil de ler.
8. Exercícios Propostos
-
Insertion Sort: Implemente o algoritmo Insertion Sort em Prolog.
Dica: Useinsere/3para inserir um elemento em uma lista ordenada. -
Quick Sort: Implemente o Quick Sort em Prolog.
Dica: Use um pivô (ex: o primeiro elemento) e divida a lista em menores e maiores. -
Bubble Sort: Implemente o Bubble Sort em Prolog.
Dica: Usetroca_uma_vez/2e repita até a lista ficar ordenada. -
Selection Sort: Implemente o Selection Sort.
Dica: Encontre o menor elemento, remova-o e ordene o resto. -
Comparação: Teste os diferentes algoritmos com listas de diferentes tamanhos e compare a eficiência em termos de tempo (use
time/1).
9. Conclusão
O Merge Sort é um exemplo perfeito de como o Prolog pode expressar algoritmos complexos de forma elegante e declarativa. Com poucas linhas de código, implementamos um algoritmo eficiente de ordenação que é:
- Correto: A recursão garante que todas as partes sejam ordenadas.
- Eficiente: O(log n) para divisão e O(n) para intercalação.
- Legível: Cada passo do algoritmo é claramente expresso em Prolog.
Dominar o Merge Sort em Prolog é um excelente exercício para entender como a recursão, a unificação e a divisão de listas se combinam para criar soluções poderosas.