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?

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.

Executar um comando no sistema operacional do host

Você já deve ter pensado em utilizar algum comando o sistema operacional para seus programas, não é? No meu caso, eu precisava usar o mysqldump para gerar automaticamente a exportação do meu banco de dados para backup.

A solução é simples, já que o Java nos dá todas as ferramentas para executar este comando. Não queremos somente executar o comando, mas gravar um log do que aconteceu. Podemos até mesmo interpretar este log e tomar alguma outra ação. No meu caso, mandar um email falando que o backup não funcionou.

O exemplo que eu vou apresentar abaixo não é do mysqldump, mas é simplesmente a saída de comando diskfree (df) no linux. Vamos lá!

/**
* Executa um comando simples no linux
* @author H3dema
*
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// classe principal para execucao do comando
public class DiskFree {
  public BufferedReader executa() {
    BufferedReader saidaComando = null;
    String[] linhaComando = null;
    // usamos a classe System para retornar o sistema operacional
    if (System.getProperty("os.name").equals("Linux")) {
      linhaComando = new String[2];
      linhaComando[0] = "df";
      linhaComando[1] = "-h"; // mostra "human readable"
    } else if (System.getProperty("os.name").equals("Solaris")) {
      linhaComando = new String[2];
      linhaComando[0] = "df";
      linhaComando[1] = "-k";
    }
    if (linhaComando == null) {
      return saidaComando; // não é um dos dois sistemas operacionais --> sai
    }

    Process fs = null;
    try {
      fs = Runtime.getRuntime().exec(linhaComando);
    } catch (IOException e) {
      e.printStackTrace();
      return saidaComando;
    }

    saidaComando = new BufferedReader(new InputStreamReader (fs.getInputStream()));
    return saidaComando;
  }

  public static void main(String[] args) {
    DiskFree df = new DiskFree();
    BufferedReader br = df.executa(); 
    String linhaDoBuffer = null;

    try {
      while ((linhaDoBuffer = br.readLine()) != null) {
        System.out.println(linhaDoBuffer);
      }
    } catch (IOException e) {
      System.out.println(e.getMessage());      
    }
  }
}
Neste programa utilizando algumas classes interessantes:

• System.getProperty("os name") retorna uma String com o tipo do sistema operacional 
• Para executar o programa usando uma classe Process que recebe o resultado de Runtime.getRuntime().exec(linhaComando)
• A classe Process retorna um InputStream que permite receber os resultados do comando executado. No nosso exemplo, guardamos este resultado em um BufferedReader que nos permite apresentar o resultado do comando. Mas poderíamos ler estas linhas para poder executar alguma outra ação.

O resultado do comando executado é mostrado abaixo: