Dividir e Conquistar – Merge Sort
Quando um problema pode ser dividido em vários subproblemas que são iguais ao original, porém menores em tamanho você pode resolver estes problemas recursivamente, dividindo-os em partes cada vez menores, até que sua solução seja trivial, e depois juntar o resultado das resoluções em partes maiores para se obter a solução do problema original. O nome desta técnica é Dividir e Conquistar e utiliza a recursão. Você pode ler mais sobre recursão neste artigo e também neste outro, da Wikipedia.
Portanto os três passos que esta técnica envolve, em cada nível de recursão são.
- Dividir – Dividir o problema em um conjunto de sub problemas que são instâncias menores do mesmo problema principal.
- Conquistar – Resolver os subproblemas a partir da mesma resolução recursiva. Se o tamanho do subproblema é pequeno o suficiente, aplicar uma resolução trivial.
- Combinar – Combinar a solução dos subproblemas na solução do problema original.
O algoritmo que veremos neste post se chama Merge Sort. Ele realiza o mesmo trabalho que o Insertion Sort porém em um tempo de execução bem menor, mas com o custo de memória da recursão.
O Merge Sort aplica os três passos descritos acima da seguinte maneira:
- Dividir – Divide a seqüência de “n” elementos em duas subseqüências de “n/2″ elementos cada.
- Conquistar – Ordena as duas subseqüências recursivamente com o próprio Merge Sort.
- Combinar – Combina (“Merge”, em inglês) as duas subseqüências ordenadas.
A condição de parada da recursão no Merge Sort acontece quando o array a ser ordenado têm tamanho 1. Ou seja, não há trabalho a ser feito e ele já se encontra trivialmente ordenado. Desta forma a operação principal deste algoritmo é a combinação dos arrays ordenados, no terceiro passo. Este procedimento de junção é chamado de “Merge” e é feito por uma função auxiliar.
Antes de exibirmos o algoritmo completo do Merge Sort vamos explicar e analisar um pouco melhor o algoritmo de merge.
Merge
Imagine que você têm duas pilhas de cartas de baralho e que inicialmente elas já se encontram ordenadas (com as menores cartas no topo). Nosso objetivo é formar uma única pilha a partir destas duas, de maneira que o resultado final continue ordenado. Intuitivamente o que fariamos seria:
- Pegar uma carta da pilha da direita e uma da pilha da esquerda, descobrir qual é a menor e coloca-la em uma terceira pilha (que representará o resultado final).
- Supondo que a carta menor foi a da pilha da direita, pegamos novamente outra carta da pilha da direita e comparamos novamente com a outra carta, que já estava em nossa mão (vinda da pilha esquerda).
- Repetimos os passos um e dois até que não haja cartas em ambas as pilhas. Se uma pilha se esgota primeiro, simplesmente continuamos pegando as cartas da pilha remanescente.
Como partimos da premisa que antes do processo as duas pilhas já se encontravam ordenadas, e que a cada iteração a pilha resultante também continua ordenada, podemos concluir que ao fim do processo nosso objetivo será alcançado.
O procedimeto de Merge leva tempo linear, , ou seja, o tempo de execução deste algoritmo está relacionado ao número de itens sendo ordenados. Computacionalmente cada passo leva um tempo constante já que apenas uma comparação entre os elementos do topo é feita. Já que realizamos no máximo
passos, podemos afirmar que o algoritmo de Merge leva um tempo linear.
O código apresentado abaixo apresenta esta idéia com a diferença de que adicionamos a lista de números que estamos ordenando um valor máximo, para que evitemos verificar a cada iteração se a lista já está vazia ou se chegou ao seu limite (e assim evitamos exceções de “array fora dos limites”). Chamaremos este valor de “sentinela”.
Abaixo apresento o pseudo-código do algoritmo de merge. Esta imagem foi retirada do livro Introduction to Algorithms, que tem guiado esta série de posts. Em seguida apresento uma implementação em Java Script.
A linha 1 computa o tamanho n1 do sub array A[p..q], e a linha 2 computa o tamanho n2 do sub array A[q + 1..r]. Criamos os arrays “esquerda” e “direita”, de tamanhos n1 + 1 e n2 + 1 respectivamente. Na linha 3 a posição extra em cada array guarda o valor “sentinela”. O loop for nas linhas 4-5, e 6-7 copiam os sub arrays nos novos arrays “esquerda” e “direita”. Linhas 8-9 colocam as sentinelas no fim dos arrays. As linhas 10 a 17 representam os passos para reordenar os valores dentro do array principal.
A implementação em Java Script abaixo contém algumas modificações em relação aos indices já que os arrays em Java Script iniciam em zero, e a notação do livro adotou o inicio em 1. O array não é retornado pois arrays são passados por referência. Se você usa o browser Chrome é muito fácil testar este código, caso use Windows aperte Control – Shift – J, caso use Mac, aperte Command – Option – J então copie e cole este código no console de testes do navegador. Passe alguns valores para a função Merge e verifique o resultado.
Abaixo segue uma versão em C#, bem mais legivel, na minha opinião, porém trabalha recebendo as duas listas já prontas ao invés de extrai-las do array principal.
Merge Sort
Abaixo mostramos o pseudo código do Merge Sort e em seguida sua implementação em JavaScript. Perceba que na linha 3 o valor da divisão é truncado.
Em resumo, o algoritmo divide a coleção em duas, e chama o algoritmo recursivamente em ambas as partes, até que seu tamanho seja unitário, nessa ocasião a recursão inicia seu retorno e o algoritmo de merge as junta em um pedaço ordenado maior, a medida que a recursão volta todas as partes ordenadas são juntadas até que o array principal esteja completamente ordenado.
A análise de algoritmos do tipo “Dividir e Conquistar” será feita no próximo post da série de análise de algoritmos.
