Dividindo e conquistando - O algoritmo Merge Sort

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar. Hoje abordaremos mais um tópico da série: Vamos por ordem nessa bagunça ? - Algoritmos de ordenação

Clique para dar uma olhada.

Neste post aprenderemos o algoritmo de ordenação Merge Sort.

AVISO: Esse algoritmo não é para iniciantes logo, você vai precisar de algum tempo para entendê-lo. Procure a supervisão de um adulto. =)

A nossa primeira pergunta é: como ele funciona ?

Criado por John von Neumann em 1945, este algoritmo utiliza a técnica de dividir para conquistar, diferentemente do seu primo, o algoritmo Bubble Sort. Possui complexidade de tempo Θ(n log 2n), no pior caso e no melhor caso, Θ(n log n).

Figura 1 - Criador do algoritmo Merge Sort

O algoritmo Merge Sort é de fácil implementação. É conceitualmente mais fácil do que a ordenação quicksort e a ordenação Shell mas, possui uma desvantagem. Requer um vetor adicional na memória, igual em tamanho àquele sendo ordenado. Se seu vetor original mal couber na memória, a ordenação não funcionará. Porém, se você possuir bastante espaço, isso não será um problema.

Sua estratégia consiste em criar uma sequência ordenada a partir de outras duas já ordenadas. Para tal, divide-se a sequência original em pares de dados, e ordena-se. Depois, agrupa-se em sequências de quatro elementos, e assim por diante até a sequência original estar separada em apenas duas partes. Este processo se repete até o array estar totalmente unido e ordenado.

A imagem abaixo ilustra bem o explicado.

Figura 2 - Funcionamento do algoritmo Merge Sort

Interprete cada faixa da imagem como uma etapa, ou seja, na primeira etapa é quando o array está todo unido, e assim por diante. É possível notar claramente como esse algoritmo funciona. Na primeira etapa temos o array todo unido, na segunda já dividimos ele ao meio (a divisão não é exata porque o tamanho do array não é par), ou seja, já estamos utilizando da técnica dividir para conquistar e esse processo de divisão se repete até a etapa 4.

Na etapa 4 dividimos o array até o máximo, ou seja, quando sobra somente 1 elemento, esse é o nosso caso base. A partir daí, podemos começar a ordená-lo. Na etapa 5 realizamos a primeira ordenação, ou seja, a ordenação dos pares. A partir da ordenação dos pares, podemos unir eles e ordená-los novamente, Esse processo se repete até o ponto em que obtemos o array todo unido novamente só que, agora ordenado.

O gif abaixo mostra todo o processo de ordenação de forma animada.

Figura 3 - Animação de funcionamento do algoritmo Merge Sort

Mas como transformar toda essa inteligência em um programa Java ?

1:  public class MergeSort {  
2:       private int[] numbers;  
3:       private int[] helper;  
4:    
5:       private int number;  
6:    
7:       public void sort(int[] values) {  
8:            this.numbers = values;  
9:            number = values.length;  
10:            this.helper = new int[number];  
11:            mergeSort(0, number - 1);  
12:       }  
13:    
14:       private void mergeSort(int begin, int end) {  
15:            // check if begin is smaller then end, if not then the array is sorted  
16:            if (begin < end) {  
17:                 // Get the index of the element which is in the middle  
18:                 int middle = begin + (end - begin) / 2;  
19:                 // Sort the left side of the array  
20:                 mergeSort(begin, middle);  
21:                 // Sort the right side of the array  
22:                 mergeSort(middle + 1, end);  
23:                 // Combine them both  
24:                 merge(begin, middle, end);  
25:            }  
26:       }  
27:    
28:       private void merge(int begin, int middle, int end) {  
29:    
30:            // Copy both parts into the helper array  
31:            for (int i = begin; i <= end; i++) {  
32:                 helper[i] = numbers[i];  
33:            }  
34:    
35:            int i = begin;  
36:            int j = middle + 1;  
37:            int k = begin;  
38:            // Copy the smallest values from either the left or the right side back  
39:            // to the original array  
40:            while (i <= middle && j <= end) {  
41:                 if (helper[i] <= helper[j]) {  
42:                      numbers[k] = helper[i];  
43:                      i++;  
44:                 } else {  
45:                      numbers[k] = helper[j];  
46:                      j++;  
47:                 }  
48:                 k++;  
49:            }  
50:            // Copy the rest of the left side of the array into the target array  
51:            while (i <= middle) {  
52:                 numbers[k] = helper[i];  
53:                 k++;  
54:                 i++;  
55:            }  
56:       }  
57:  }  

Pronto, conseguimos !! Vamos entender agora como o programa Java implementa o algoritmo.

Classe MergeSort

Essa classe possui os métodos de ordenação e os atributos numbers, helper e number os quais representam respectivamente, o array de valores, o array auxiliar e a variável usada para armazenar o tamanho do array de valores.

Esta implementação já possui uma otimização implementada para o problema de memória citado acima. Da forma que foi projetado, o array auxiliar só é carregado uma vez em memória visando aliviar o consumo.

Método sort

Esse método recebe o array original e realiza as seguintes operações:

• Linha 8: passa os valores do array, recebido como parâmetro, para o array atributo, numbers.
• Linha 9: Define o valor do atributo number onde, esse valor é o tamanho do array original.
• Linha 10: Define a dimensão do array auxiliar onde, essa dimensão é a mesma do array original.
• Linha 11: Realiza a chamada ao método mergeSort, passando como parâmetros o número 0 e o resultado da operação number - 1 onde, zero representa o início de qualquer array e number - 1 representa a última posição do array.

Método mergeSort

Esse método realiza a divisão já citada acima. Recebe dois parâmetros: a posição inicial e final do array.

• Linha 16: Verifico se o parâmetro begin é menor que o parâmetro end. Essa verificação é necessária pois, ela realiza o controle da divisão do array. Caso a condição não seja verdadeira é porque o array está vazio ou, já está ordenado.
• Linha 18: Calculo o meio do array visando a divisão do mesmo.
• Linha 20: Realizo chamada recursiva passando como parâmetros begin e middle, ou seja, estou analisando a primeira metade do array dividido. Como esta é uma chamada recursiva, as linhas anteriores (16 e 18) serão executadas novamente, até o momento em que reste somente uma posição no array dividido n-vezes.
• Linha 22: Realizo chamada recursiva passando como parâmetros middle +1 e end, ou seja, estou analisando a segunda metade do array dividido. O processo de divisão segue de forma igual ao citado acima.
• Linha 24: Realizo chamada ao método merge passando os parâmetros: begin, end e middle. Dependendo do nível de recursividade da execução do algoritmo, os valores dessas variáveis não estarão iguais as que estavam originalmente.

Método merge

Esse método realiza a ordenação. Recebe três parâmetros: a posição inicial, final e média do array.

• Linha 31 até 33: Copia os valores do array original para o array auxiliar. Os valores copiados são limitados pelo intervalo definido pelas variáveis begin e end.
• Linha 35 até 37: Declaro as variáveis i, j e k.
• Linha 40 até 49: É aqui aonde a mágica acontece. A condição definido no loop while da linha 40 define que a iteração será feita do início da fatia esquerda até seu fim e depois do início da parte direita até seu fim. Essa condição é definida dessa forma porque sempre comparamos o grupo da esquerda com o da direita. Na imagem ou no gif animado é possível notar isso. Nas linhas 41 e 44, é avaliado quem é menor valor. Caso o valor da esquerda seja o menor, ele é copiado para o array original na posição certa (k) e a variável i é incrementada, caso contrário, o valor da direita é copiado e a variável j é incrementada. A variável k é incrementada fora do bloco condicional if pois, ele representa a posição final do valor ordenado logo, ele não precisa estar sendo incrementado onde é avaliado o menor valor e sim, depois que isso foi feito.
• Linha 51 até 55: Nesse bloco são copiados os valores restantes da ordenação. O bloco acima não deixa o array original totalmente ordenado, ele só passa os menores valores para frente (ordenação crescente). Então, precisamos de uma outra iteração para recuperar os outros valores do array auxiliar e posicioná-los nas posições corretas. Como sabemos quais as posições corretas ? A variável k não é zerada logo, ele ainda guarda referência do último valor ordenado posicionado. As variáveis i e k devem ser incrementadas para realização do posicionamento.

Cumprimos mais uma etapa do nosso estudo. Entendemos a implementação do nosso programa. Vamos realizar alguns testes ?

Nossos testes serão feitos da seguinte forma: iremos montar um array um valores aleatórios e com as dimensões da primeira coluna. Depois de montado, iremos realizar a operação de ordenação 1 milhão de vezes e medir o tempo total. O tempo individual de cada processamento é calculado pela divisão do tempo total por 1 milhão.

Figura 4 - Testes feitos para medir a execução do algoritmo

Gráfico gerado a partir da planilha.

Figura 5 - Gráfico de quantidade de elementos por tempo

Através das evidências acima podemos notar que, conforme multiplicamos por 10 a quantidade de números, o resultado final também cresce da mesma forma. Esse algoritmo se mostrou eficaz para uma grande quantidade de números visto que, seu primo, Bubble Sort, demorou muito mais tempo.

Para fazer o download do algoritmo, clique aqui.

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários ou na nossa página do facebook.

Facebook: https://www.facebook.com/precisoestudarsempre/

Referências:
Merge sort - https://pt.wikipedia.org/wiki/Merge_sort
John von Neumann - https://pt.wikipedia.org/wiki/John_von_Neumann
Gif Merge Sort - https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif
Program: Implement merge sort in java. - http://java2novice.com/java-sorting-algorithms/merge-sort/
Mergesort in Java - Tutorial - http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html
Estruturas de dados e algoritmos em Java, Robert Lafore, 2004