quinta-feira, 21 de junho de 2012

Algoritmo Bubble Sort

Espero que vocês tenham gostado do post anterior sobre ordenação. Vamos ver um clássico neste post. O algoritmo de ordenação da bolha.

Este algoritmo é "facinho" para utilizar o mineirez. Ele basicamente faz:
  1. Percorre o vetor inteiro comparando elementos adjacentes (dois a dois)
  2. Troca as posições dos elementos se eles estiverem fora de ordem
  3. Repete os dois passos acima com os primeiros n-1 itens, depois com os primeiros n-2 itens, até que reste apenas um item
Este método só é adequado para arquivo pequeno, pois realiza muita atividade porque o número de operações não altera se o vetor for (parcialmente) ordenado. É possível melhor terminando a execução quando nenhuma troca é realizada após uma passada pelo vetor. No nosso exemplo abaixo vamos utilizar a forma clássica, isto é, sem esta melhoria, para vocês verem como ele é fácil de entender e ruim de executar.

/*
Exemplo utilizando Algoritmo Bubble Sort
*/

import java.util.Vector; // vamos usar Vector ao invés de Array
                         // só para complicar um pouco
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.lang.NumberFormatException;


public class BubbleSort {

   private static void bubbleSort(Vector<Integer> v) {
      int n = v.size(); // qtd de elementos do vetor
      int temp = 0; // armazena valor temporário para efetuar as trocas
              
      for(int i=0; i < n; i++){
         for(int j=1; j < (n-i); j++){
             if(v.get(j-1) > v.get(j)){
               //swap the elements!
               temp = v.get(j-1);
               v.set(j-1, v.get(j));
               v.set(j, temp);
             } // if
         } // for j
         // para fins didáticos, imprimimos cada passo
         System.out.println("Vetor passo " + i + " : " + v);
      } // for i
   } // bubbleSort

   public static void main(String[] args) {
              
      // cria o vetor
      Vector<Integer> v = new Vector<Integer>();
      // preenche o vetor com os dados do arquivo
      String nomeArquivo = "dados.txt";
      try {
         BufferedReader in = new BufferedReader(new FileReader(nomeArquivo));
         String linha = null;
         while ((linha = in.readLine()) != null) {
           try {
             v.add(Integer.valueOf(linha));
           } catch (NumberFormatException e1) {
             // somente não insere
           } // try
         } // while
         in.close();
      } catch (IOException e) {
         System.out.println( "erro não tratado - somente indicação ");
      } // try

      System.out.println("Vetor não ordenado : " + v);

      //ordena o array com bubble sort
      bubbleSort(v);

   } //main

}

Vamos ver a saída:
Pulamos alguns (!!!) passos:

Fim! Ordenou!
O que vocês acham? Usar este ou o método do post anterior?

quarta-feira, 20 de junho de 2012

Ordenando dados em Java

Oi Pessoal,

Depois de um longo e tenebroso inverno ;-) voltei a postar aqui para vocês. Estou fazendo um curso que está me tomando um pouco de tempo, mas vamos lá.

Estive precisando de fazer umas ordenações de dados em java recentemente. Vejam que coisa legal esta Interface Comparator.

/*
  Este programa ordena um Vector em ordem decrescente/crescente
  utilizando a Interface Comparator
 
  os dados de entrada são obtidos de um arquivo de texto cujos dados estão
  inseridos um por linha
*/

import java.util.Vector;
import java.util.Collections;
import java.util.Comparator;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.lang.NumberFormatException;

public class ExemploOrdenaVector {

  public static void main(String[] args) {
  
    // cria o vetor
    Vector<Integer> v = new Vector<Integer>();
 
   // entrada de dados a partir do arquivo de texto
   // utilizei a leitura com BufferedReader
   // o loop preenche o vetor com os dados do arquivo
   // utilizo método valueOf para converter a string em inteiro
    String nomeArquivo = "dados.txt";
    try {
      BufferedReader in = new BufferedReader(new FileReader(nomeArquivo));
      String linha = null;
      while ((linha = in.readLine()) != null) {
        try {
          v.add(Integer.valueOf(linha));
        } catch (NumberFormatException e1) {
          // somente não insere
        }
      }
      in.close();
    }
    catch (IOException e) {
      System.out.println( "erro não tratado - somente indicação ");
    } 

    System.out.println("Vetor não ordenado : " + v);
 
    // Para ordenar um vetor devemos utilizar:
    //  static void sort(List list, Comparator c)
    //
    // como queremos na ordem inversa usamos Collections.reverseOrder()  
    Comparator comparator = Collections.reverseOrder();
    Collections.sort(v,comparator);
    System.out.println("Vetor ordenado (DESC) : " + v);

    Collections.sort(v); // chamada igual sem o reverseOrder
    System.out.println("Vetor ordenado (ASC) : " + v);
  
  }
}

Vamos ver este exemplo rodando:
Como esperado!!

O bacana deste código é que ele pode ser facilmente adaptado para qualquer tipo de dado. Vamos ver por exemplo para string. Temos que trocar somente 3 linhas:

  • trocar o tipo do vetor para string
    Vector<String> v = new Vector<String>();



  • trocar o arquivo de dados. só porque eu coloquei fixo no código. vejam que não muda nada no algoritmo de leitura...
    String nomeArquivo = "dados2.txt";

  •  exceto a adição da linha ao vetor. agora não preciso fazer conversão
    v.add(linha);



Fantástico, não é?

PS: para quem ficou curioso com o texto... É Lusíadas de Camões.