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?