Bubble Sort em Java

Publicado por Mariana Ribeiro Mendes (última atualização em 29/09/2012)

[ Hits: 8.376 ]

Download BubbleSort.java




Bubble Sort

É um dos algoritmos mais simples e é indicado apenas para quando se há uma pequena quantidade de dados. Sua implementação é simples, ele percorre uma lista de dados várias vezes, e em cada passagem pela lista ele leva o maior elemento que ele encontrar naquela sequencia para o final (última posição possível para sua colocação).

Complexidade do pior caso:  O (n²)
Complexidade do caso médio: O(n²)
Complexidade do melhor caso: n

Espero que gostem. Qualquer dúvida ou discordância, sintam-se livres para me contatar.

Abraços.

  



Esconder código-fonte

import java.util.Scanner;


//Inicio da classe BubbleSort
public class BubbleSort {

    //Método bubbleSort, ele é quem faz a ordenação
    public static void bubbleSort (int[] dados){
 
        /**
         * Inicia a variável que verifica se houve alguma troca entre os items.
         * Ela é inicializada como true para poder entrar no laço que garantirá que o
         * vetor seja organizado até o final, quantas vezes forem necessárias.
         */
        boolean troca = true;
        
        
        //Laço que garante que o vetor seja verificado quantas vezes forem necessárias
        while (troca) {
            
                /**
                 * Muda o estado da variável troca para que o laço funcione corretamente.
                 * Se ela entrar no for, e seu estado não for mudado para true, significa que não
                 * são mais necessárias verificações no vetor.
                 */
                troca = false;
                
                /**
                 * Este for realiza apenas uma volta no vetor, o que pode não ser suficiente
                 * para a total organização dos itens.
                 */
                for (int posicao = 0; posicao < (dados.length)-1; posicao++){
                    
                        /**
                         * Se o dado da posição atual for maior que o dado da próxima posição, 
                         * é realizado uma troca entre eles.
                         */
                        if (dados[posicao] > dados[posicao+1]){
                            
                                //Copia o valor da próxima posição para uma variável auxiliar
                                int variavelAuxiliar = dados[posicao+1];
                                //Coloca o valor da posição atual na próxima posição
                                dados[posicao+1] = dados[posicao];
                                //A posição atual recebe o valor que foi copiado para a variável auxiliar
                                dados[posicao] = variavelAuxiliar;
                                /**
                                 * Seta true para a troca, indicando que houve troca, evitando assim que 
                                 * o vetor não seja verificado uma próxima vez. 
                                 * Caso o vetor seja percorrido sem trocas, a variável continuará false
                                 * indicando que não há mais necessidade de verificações no vetor.
                                 */
                                troca = true;
                                
                        }
                }
        }     
        
        //Chama uma função para exibir os dados já organizados.
        imprime(dados);
} //Fim do bubbleSort
    
    //Função que imprime os dados organizados.
    public static void imprime(int[] dados){
        
         //Para cada iteração do for, ele imprime o dado que estiver na posição indicada pelo variável.
         for (int posicao = 0; posicao < dados.length; posicao++ ){
            
            System.out.println(dados[posicao]);
        
        }
        
        
    }
    
    
    //Função principal, onde começa a execução.
    public static void main(String[] args) {
        
        //Cria um vetor de 10 posições.
        int[] dados = new int[10];
        
        //Cria uma instancia de Scanner para realizar a leitura dos valores.
        Scanner in = new Scanner(System.in);
        
        //Para cada iteração do for ele lê um valor.
        for (int posicao = 0; posicao < dados.length; posicao++ ){
            
             System.out.println("Entre com um valor");
             dados[posicao] = in.nextInt();
        
        }
        
        //Chama o método bubbleSort para ordenar os dados recebidos.
        bubbleSort(dados);
        
        
    }
}

Scripts recomendados

Começando a trabalhar com arrays

Programa de sorteio

Verifica se é triângulo

Trabalhando com Cores

Separador de algarismos


  

Comentários
[1] Comentário enviado por MAPOGOS em 11/10/2012 - 22:15h

Em oq significa complexidade
de
Complexidade do pior caso: O (n²) -------------------Isto é O (N²) UM ALGORITMO Q MULTIPLICA N ELEVADO AO QUADRADO???
Complexidade do caso médio: O(n²)-------------------sto é O(N²) UM ALGORITMO Q MULTIPLICA N ELEVADO AO QUADRADO???PORQ ELE ESTA JUNTO AGORA DO PARENTESES.
Complexidade do melhor caso: n isto é só um caracte???

[2] Comentário enviado por meldenne em 11/10/2012 - 22:39h

Complexidade de algoritmos, é um estudo feito sobre a quantidade de trabalho necessário que o algoritmo tem para executar uma determinada função. Ela é utilizada na computação para fazer comparações entre algoritmos, determinar se um é melhor que o outro e em que situação ele é melhor.

Neste caso (bubble sort) :

O O(n²) do pior caso, quer dizer que, dada um entrada de tamanho N (n dados), ele terá de fazer n² operações para ordenar a lista de dados. No caso médio a situação é a mesma.
No melhor caso O(n), quer dizer que ele terá que fazer apenas N operações.

Basicamente é isso que quer dizer, mas há muitas outras complexidades. Há muitos conceitos além disso.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts