Vamos por ordem nessa bagunça ? - Algoritmos de ordenação

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Hoje faremos algo diferente e inusitado aqui. Esse post será um catálogo para outros posts. Você pode estar se perguntando: "catálogo de que ?"

Bem, acredito que o nome do post é bem sugestivo, nosso catálogo será sobre algoritmos de ordenação e lá vem a sua segunda pergunta: " Porque criar um catálogo e não por o conteúdo logo aqui ?! "

A resposta é simples, algoritmo de ordenação é um assunto grande então, se eu fosse por todos os algoritmos aqui, não poderia dar a atenção devida pra cada um, o post ficaria extenso e isso acabaria cansando sua leitura. Tento escrever da melhor forma possível para que o conteúdo fique legal você, caro leitor.

Para cada novo post sobre ordenação lançado, vou atualizar esse post aqui, botando o link para o post recém criado. Espero que nosso catálogo fique imenso e que você se torne um expert nos algoritmos de ordenação.

Catálogo de algoritmos de ordenação

1. Algoritmo BubbleSort - http://precisoestudarsempre.blogspot.com.br/2015/09/bolhas-no-tanque-o-algoritmo-bubble-sort.html
2. Algoritmo Merge Sort - http://precisoestudarsempre.blogspot.com.br/2015/11/dividindo-e-conquistando-o-algoritmo.html
3. Algoritmo Insertion - http://precisoestudarsempre.blogspot.com.br/2016/03/inserindo-as-coisas-certas-nos-lugares.html
4. Algoritmo Shell Sort - http://precisoestudarsempre.blogspot.com.br/2016/08/a-criacao-de-donald-shell-o-algoritmo.html
5. Algoritmo Selection Sort - https://precisoestudarsempre.blogspot.com.br/2017/10/aprendendo-escolher-bem-o-que-por-em.html

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/

Leia Mais ››

Bolhas no tanque - O algoritmo Bubble Sort

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Este é o primeiro post da nossa série sobre algoritmos de ordenação e vamos começar com aquele algoritmo mais primordial que nos acompanhou em todo o período da faculdade, o Bubble Sort. Se você ainda não passou por isso, relaxe pois, passará. Se você já passou e não entendeu como ele funciona, agora é o momento da decisão.

O estudo que faremos aqui envolverá a construção do algoritmo em Java e alguns experimentos. Não usaremos ferramentas de desenvolvimento ultra modernas, um simples editor de texto bastará.

Qual é a lógica por trás desse algoritmo ? É simples, sua lógica consiste na troca da posições dentro do array de elemento por elemento, analisando quem tem o maior valor. O elemento de maior valor vai sendo movimentado para o fundo do array, até encontrar alguém maior que ele. Caso encotnre, o antigo maior valor pára de ser movimentado e o novo maior valor começa a ser movimentado para o fundo do array, respeitando a regra mencionada acima

Ficou confuso ? Vamos entender melhor.

Figura 1 - Funcionamento do algoritmo Bubble Sort

No gif animado acima é possível ver quer os elementos são avaliados par a par. Se o primeiro elemento do par for maior que o segundo ele é trocado de lugar, por exemplo os valores 6 e 5.

Figura 2 - Primeiro par escolhido

Após a troca de lugar, é avaliado o segundo par: 6 e 3.

Figura 3 - Segundo par escolhido

As trocas são realizadas somente se o primeiro elemento for maior que o segundo. Caso não seja, um novo par é escolhido. No gif animado é possível ver que em um determinado momento, o 6 forma par com o 8 mas, 6 não é maior que 8 logo, ele não é trocado e um novo par é feito. Todo este processo é repetido até que o array esteja ordenado.

Agora sim, temos tudo o que precisamos para construir nosso algoritmo.

      public void sort(int[] array, int tamanho){  
           int aux;  
   
           for(int i=tamanho-1; i >= 1; i--) {   
                for(int j=0; j < i ; j++) {  
                     if(array[j]>array[j+1]) {  
                          aux = array[j];  
                          array[j] = array[j+1];  
                          array[j+1] = aux;  
                     }  
                }  
           }  
      }  

O algoritmo é bem simples e tem complexidade O(n²) no pior caso. O segundo for executa uma varredura no sentido início - fim, avaliando se o primeiro elemento da dupla é maior que o segundo. O responsável pela troca de posições é o bloco de código dentro do if. O primeiro for trabalha de forma fim - início a fim de otimizar o algoritmo visto que, uma vez que o elemento de maior valor é jogado para o fim do array, não existe motivo para que uma dupla seja composta com esse valor. É possível ver isso acontecendo no gif animado, no momento em que o 8 (maior valor) é jogado para o fim do array.

Ótimo !!! Atingimos mais uma etapa. Primeiramente, entendemos a lógica do algoritmo e logo em seguida, vimos uma possível implementação. Para fechar com perfeição, vamos fazer algumas análises de tempo de processamento.

Dadas as situações testadas abaixo:

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

As quais geraram o seguinte gráfico:

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

É possível notar que conforme o número de elementos cresce de forma quadrática, o tempo do algoritmo cresce seguindo a família do 100, ou seja, 100 vezes, 200 vezes, etc.. Se continuássemos os testes para dez mil ou cem mil iríamos notar um aumento ainda maior no tempo de execução. Tal algoritmo, se aplicado a situações da vida real onde, a dimensão do problema pode ser maior ou menor que os testados aqui, pode gerar um certo atraso ou não, na execução do programa como um todo.

E com isso, terminamos o nosso estudo sobre o algoritmo Bubble Sort. Espero que você tenha gostado. Caso note alguma anomalia nos testes realizados, deixe sua contribuição nos comentários.

Para baixar o 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:
Comparison Sorting Algorithms - https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.htmlA Comparative Study between Various Sorting Algorithms - http://paper.ijcsns.org/07_book/201503/20150302.pdf
Sorting Algorithm Animations - http://www.sorting-algorithms.com/
Bubble sort - https://pt.wikipedia.org/wiki/Bubble_sort

Leia Mais ››

OGNL + Struts 2 - Porque causa tanta confusão ?

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

O tema de hoje é voltado para desenvolvedores que já estão familiarizados com o framework Struts 2.  Não explicarei aqui como funcionam as tags do Struts pois, não é esse o nosso objetivo. Caso você, amiguinho, não conheça nada desse framework, recomendo fortemente que você dê uma clicada aqui e veja essa listagem de tutoriais.

Tenho experiência de alguns anos com o framework Struts 2 e toda vez que preciso recuperar dados usando OGNL, me sinto um pouco inseguro e desconfortável mas, porque ? Tenho de admitir que sou muito fã de Expression Language (EL) + JSTL porque, com eles consigo trabalhar de forma límpida e rápida. A verdade era que a OGNL não descia pela minha garganta porque, achava muito complicado, existem várias formas de se fazer a mesma coisa. Eu nunca sabia quando usar o #, o %{expressão}, o @ ou o attr e isso ainda podia piorar porque, as vezes via em alguns exemplos, pessoas realizando combinações desses caracteres. Isso tudo me estressava profundamente, eu não conseguia entender o que eu tinha de fazer e acabava testando combinações aleatórias, esperando a primeira funcionar. Porém, como o nosso foco não pode conhecer limites, tive que aprender OGNL e gostar dela.

A OGNL não é nada mais, nada menos que um tipo de linguagem de escopo de página, usada para recuperar dados dos diferentes contextos de uma aplicação. Antes que você me pergunte se é possível utilizar OGNL com outro framework que não seja o Struts 2, eu te respondo que nunca vi tal integração. Nem com o Struts 1, acho que é possível.

Depois de um certo tempo de pesquisa, consegui achar uma resposta para minha penosa dúvida. Tal resposta a qual, servirá para construir exemplos em uma aplicação web mostrando que a mesma é verídica. Então, aperte seus cintos.

Como disse anteriormente, a OGNL é usada para recuperar valores de um determinado escopo onde, esse escopo pode ser request, sessão ou aplicação. Porém, antes de sabermos de qual escopo queremos recuperar nosso dado, precisamos saber qual o seu nome logo, sempre que usarmos OGNL temos que especificar qual o nome do nosso objeto (objectName) tanto, para simples recuperações quanto, para montagem de expressões. Esta é a nossa premissa básica.

Vou separar as explicações por perguntas, acho que assim fica mais fácil para você encontrar.

• Quando uso o # ? 

Usamos a tralha ou jogo da velha para fazer referência a objetos que estejam no nosso ActionContext, ou seja, no contexto da nossa action. Como assim ?

• #objectName - Objeto que tenha sido criado usando as tags do struts com o escopo padrão.
• #parameters.objectName - Um parâmetro do request.
• #request.objectName  - Um atributo de escopo de request.
• #session.objectName  - Um atributo de escopo de sessão.
• #application.objectName  - Um atributo de escopo de aplicação.
• #attr.objectName  - Um atributo que pode estar nos seguintes contextos: page, request, session ou application. A busca é feita nessa ordem.

Exemplo:

Figura 1 - Primeiro exemplo do uso da #

Figura 2 - Segundo exemplo do uso da #

Note que utilizarmos a OGNL sem as tags do Struts, as expressões são renderizadas como se fossem texto. É possível recuperar valores de um determinado escopo das seguintes formas:

• #escopo.objectName
• #escopo['objectName']

Se você entendeu o uso do # então, você já entendeu 75% do uso da OGNL no Struts 2. Parabéns, você já entendeu o mais complicado.

• Quando uso o %{expressão} ?

Usamos o %{expressão} para forçar a OGNL avaliar o dado pelo seu real tipo ou para invocar um método, como por exemplo o método getText (usado para obter valores de arquivos de propriedades).

Figura 3 - Exemplo de uso do %{expressão}

Acima existem dois testes. Duas estruturas condicionais foram montadas, a primeira em cima de um atributo de um objeto e a segunda baseada em um atributo Integer da action. No primeiro if é necessário usar o %{} pois o Struts não conhece o tipo do objeto pessoa logo, ele não consegue fazer a comparação mas, como a segunda é feita em cima de um atributo do tipo Integer, não é necessário o uso do %{}. Condições realizadas em cima de tipos primitivos e seus wrappers não necessitam do %{}.

 <s:set name="var" value="%{myDinamicValue}" />  
   
 <s:set name="var" value="myDinamicValue" />  

No exemplo acima, o valor da nossa variável var, será o valor da variável myDinamicValue e no segundo exemplo, o valor final de var será a String myDinamicValue.

• Quando uso o @ ?

Usamos a @ quando queremos fazer referência a recursos estáticos, ou seja, propriedades e métodos. Para utilizar essa facilidade, você deve habilitá-la em seu arquivo struts.xml, adicionando a propriedade: struts.ognl.allowStaticMethodAccess=true.

IMPORTANTE: A partir da versão 2.3.0, o acesso a recursos estáticos através de OGNL é deprecated.

Exemplo:

Figura 4 - Exemplo de uso do @

• Quando usamos o $ ?

A OGNL não faz uso do $ logo, não irá funcionar. Caso você já tenha visto o uso do dólar acompanhado de chaves em tags do Struts 2, resultará em erro ou, em uma String comum.

Para baixar o projeto, 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:
What's the difference between # , % and $ signs in Struts tags - http://stackoverflow.com/questions/8007858/whats-the-difference-between-and-signs-in-struts-tags

Leia Mais ››