domingo, 29 de novembro de 2015

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 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

Leia Mais ››

terça-feira, 10 de novembro de 2015

Non-break space, já ouviu falar ? - Regex em Java

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar. O que vamos ver hoje aqui é como identificar non-breaking spaces através de uma regex. Se você não sabe o que é uma regex ou, não está familiarizado com elas, recomendo que você dê uma olhada nos posts aqui do blog.

Mas, o que é um non-breaking space ?

Segundo a Wikipedia:
In word processing and digital typesetting, a non-breaking space (" ") (also called no-break space, non-breakable space (NBSP), hard space, or fixed space) is a space character that prevents an automatic line break at its position. In some formats, including HTML, it also prevents consecutive whitespace characters from collapsing into a single space.
In HTML, the common non-breaking space, which is the same width as the ordinary space character, is encoded as &nbsp; or &#160. In Unicode, it is encoded as U+00A0.
Resumindo: Um non-breaking space é um caractere em branco que evita uma quebra automática de linha em sua posição. Em HTML, o non-breaking space tem a mesma largura que o caractere espaço e codificado como &nbsp; ou &#160. Em Unicode, é codificado como U+00A0.

OBSERVAÇÃO: Não sei se você notou mas o mnemônico &nbsp tem as mesmas iniciais que non-breaking space. Coincidência ? Acho que não.

Já podemos construir nossa regex em Java ? A resposta é: sim.

 [\\s\\xA0]+  

Vamos entender melhor ?
  • \\s -> Representa um whitespace (caractere em branco).
  • \\xA0 -> Representa o non-breaking space. O \\x é usado para representar um caractere com valor hexadecimal. No nosso caso, o valor é 0xA0.
  • [ ] -> Representam a operação booleana or. No nosso caso queremos identificar ou espaços em branco ou non-breaking spaces.
  • + -> Representa um quantificador. Denota que algo pode se repetir 1 ou infinitas vezes.
Possível pergunta: "Porque na regex você quer capturar também whitespaces ? Não deveriam ser somente os non-breaking spaces?"

A resposta para essa pergunta é bem simples. Eu faço isso para fins de complementação da regex, ou seja, capturando os dois tipos de espaços, eu possuo uma regex mais completa mas, nada me impede que só tenha uma regex que capture espaços em branco ou só non-breaking spaces.

No caso de dúvida sobre os elementos que compõem a nossa regex, você pode dar uma olhada na documentação do Java, clicando aqui ou, dando uma olhada nas referências abaixo.

Diferentemente dos outros posts aqui do blog onde, na maioria das vezes existe um projeto prático, dessa vez eu deixo meu conselho para você, desenvolvedor, que está passando por esse problema. Caso seja importante que seus dados não cheguem sujos na base de dados, realize dois tratamentos. O primeiro é um tratamento via trim(), pode ser feito tanto em Javascript + JQuery ou, como em Java. Não existem preferências.

O segundo tratamento é a substituição dos non-breaking spaces por Strings vazias. Esse, eu recomendo fazer em Java, através do método replaceAll. Este método recebe dois argumentos. O primeiro é uma regex (lá você põe a regex que aprendemos agora) e o segundo é o caractere que será usado para substituição.

Irei deixar nas referências o link para a documentação do método replaceAll.

É isso, terminamos !!!!

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:
Unidentified whitespace character in Java - http://stackoverflow.com/questions/1702601/unidentified-whitespace-character-in-java
Non-breaking space - https://en.wikipedia.org/wiki/Non-breaking_space
Class Pattern - http://docs.oracle.com/javase/7/docs/api/java/util/regex/Pattern.html
Classe String , método replaceAll - http://docs.oracle.com/javase/7/docs/api/java/lang/String.html#replaceAll(java.lang.String,%20java.lang.String)
Leia Mais ››