Ordenando dados com o algoritmo Bubble Sort em Java

Continuando com o assunto de ordenação simples em Java, iniciado num artigo anterior, vamos neste artigo ver o algoritmo de ordenação Bubble Sort. O algoritmo Bubble Sort é um algoritmo relativamente lento em termos de performance, se comparado com os outros algoritmos de ordenação simples falados no artigo anterior, mas em termos de compreensão de código, ele é sem dúvidas o algoritmo de ordenação simples mais simples que existe! Por isso é sempre bom começar com este algoritmo, para que possamos perceber a lógica de ordenação.

A ideia básica deste algoritmo é percorrer a estrutura de ordenação várias vezes, e a cada passagem deixar os valores mais a esquerda(ou direita) ordenados, passando para lá os menores(ou maiores valores).

Implementando o bubble Sort em Java

Aqui está o código em Java do Bubble Sort, usado para ordenar um array de números inteiros. Você pode usar este algoritmo para ordenar qualquer estrutura e qualquer tipo de dados dentro da estrutura. Criaremos uma classe BubbleSort, que irá conter um array e os métodos para inserir, mostrar, e ordenar dados. Na verdade, poderíamos adicionar o método para ordenar dados na classe para ordenar dados na classe sobre Arrays em Java , criado no artigo anterior, mas para simplificar o código, melhor criar outra classe e omitir os métodos para procurar e remover dados do array. Criaremos também uma classe TestaBubbleSort, que irá criar um array com dados aleatório, e depois irá ordena-los,para ver se o método realmente funciona. Aqui está a classe BubbleSort:

//BubbleSort.java
//Implementando o algoritmo BubbleSort em Java
//INFOmoz 23-09-08
//www.infomoz.net

public class BubbleSort
{
    private int[] a; // referência para o array
    private int nElem; // Numero de elementos no arrays

    public BubbleSort(int max) // construtor
    {
        a = new int[max]; // Criando o array
        nElem = 0; // Nenhum item ainda
    }

    public void adicionar(int valor) //Coloca um elemento no array
    {
        a[nElem] = valor; // Inserindo
        nElem++; // Incrementado o tamanho
    }

    public void imprime() // Mostra o conteudo do array
    {
        for(int j=0; j1; j--) // Loop externo(decrescente)
        for(i=0; i a[i+1] ) // Nao ordenado?
        troca(i, i+1); // Troca ele
    } // Fim do metodo BubbleSort

    private void troca(int i, int j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
 }

Os métodos construtor, adicionar() e imprimir() não trazem nada de novo, são praticamente os mesmos que os que criamos quando estávamos falando de arrays em Java. Mas existe um método novo: bubbleSort(). Quando esté método é invocado, os elementos dos arrays são ordenados.

Agora precisamos da classe de teste, para ver se o método funciona. Aqui vai ela:

import java.util.Random;
public class TestaBubbleSort
{
    public static void main (String[] args)
    {
        Random rn=new Random(); //Para gerar numeros aleatorios
        BubbleSort bs=new BubbleSort(10); //criando um array de 10 elementos
        for(int i=0;i<10;i++) bs.adicionar(rn.nextInt(100)); //Adicionando numeros aleatorios entre 0 e 100

        bs.imprime();//Mostrando os valores inseridos

        bs.bubbleSort(); //Ordenando estes valores

        bs.imprime();//Mostrando os valores ordenados

    }

}

O método main() adiciona 10 números inteiros aleatórios no array, mostra os itens no array, invoca o método bubbleSort() para ordena-los e depois exibe o array depois de ordenado. O método bubbleSort possui apenas quatro ou cinco instruções. Veja abaixo:

public void bubbleSort()
{

     int i, j;
     for(j=nElem-1; j>1; j--) // Loop externo(decrescente)
     for(i=0; i a[i+1] ) // Nao ordenado?
     troca(i, i+1); // Troca ele
 } // Fim do metodo BubbleSort

A ideia é colocar o menor elemento no inicio do array e o maior na última posição. O loop externo, tem o seu inicio na última posição do array, e vai se auto decrementando em cada loop. Os elementos que possuem um índice maior que j já estão completamente ordenados, pois a a variável j se move para a esquerda em cada loop, deixando os elementos mais a direita ordenados. Estes elementos já ordenados não farão parte do algoritmo na próxima iteração.

O loop interno começa no inicio do array, e para cada posição i que toma, vai comparando o valor neste índice com o valor no índice i+1. Se i for maior que i+1, então eles devem ser trocados, usando a função(método) externo troca()

Invariante de um algoritmo

Em muitos algoritmos existem condições que nunca devem mudar ao longo da execução do algoritmo. Estas condições são chamadas de invariantes. Reconhecer invariantes pode ser fundamental para entender o funcionamento de um algoritmo. Em certas situações esta tarefa pode ser útil para a depuração do algoritmo. Você pode analisar se a invariante continua imutável em cada loop. No algoritmo bubbleSort, a invariante é o facto dos elementos mais a esquerda estarem sempre ordenados. No inicio deste algoritmo a invariante também verifica-se, pois j é o último elemento e a esquerda não temos nenhum elemento.

Este é um dos algoritmos de ordenação mais básicos que existem. Nos próximos artigos traremos mais algoritmos.
Considere inscrever-se aqui no blog para receber nossas actualizações por email ou no Twitter.

Escrito por on 02/10/2008. Arquivado em Artigos, Java, Programação. Você pode seguir as respostas a esse artigo pelo RSS 2.0. Você pode deixar respostas para esse artigo
  • http://twitter.com/narunina/status/25201821242 Bruu =)
  • http://twitter.com/mznoticias/status/28735849436 Notícias Moçambique

    Ordenando dados com o algoritmo Bubble Sort em Java http://bit.ly/bk7TV1

  • http://twitter.com/atitudegringo/status/28735853936 ATITUDE GRINGO

    Ordenando dados com o algoritmo Bubble Sort em Java http://bit.ly/bk7TV1

  • http://twitter.com/infomoz/status/28735859166 Elisio Leonardo

    Ordenando dados com o algoritmo Bubble Sort em Java http://bit.ly/bk7TV1

  • Luana

    estou tentando compilar esse código mas aparece erro na parte:

    for(int j=0; j1; j–)
    for(i=0; i a[i+1] )
    troca(i, i+1);

    é solicitado a inclusão de ; e aparece o erro NOT STATEMENT.

    porque?