Implementando classificação por bolha em Java

Há um grande número de algoritmos de classificação, muitos deles são muito específicos e foram desenvolvidos para resolver uma gama restrita de problemas e trabalhar com tipos específicos de dados. Mas entre toda essa diversidade, o algoritmo mais simples é merecidamente o bubble sort, que pode ser implementado em qualquer linguagem de programação. Apesar de sua simplicidade, ele é a base de muitos algoritmos bastante complexos. Outra vantagem igualmente importante é a sua simplicidade e, portanto, pode ser lembrada e implementada imediatamente, sem ter nenhuma literatura adicional à sua frente.

Introdução

Toda a Internet moderna consiste em um grande número de diferentes tipos de estruturas de dados coletadas em bancos de dados. Eles armazenam todo tipo de informação, desde dados pessoais de usuários até o núcleo semântico de sistemas automatizados altamente inteligentes. Escusado será dizer que a classificação de dados desempenha um papel extremamente importante nesta enorme quantidade de informação estruturada. A classificação pode ser uma etapa obrigatória antes de procurar qualquer informação no banco de dados, e o conhecimento dos algoritmos de classificação desempenha um papel muito importante na programação.

Classificando através de olhos de máquina e olhos humanos

Vamos imaginar que você precise classificar 5 colunas de alturas diferentes em ordem crescente. Estas colunas podem significar qualquer tipo de informação (preços de ações, largura de banda do canal de comunicação, etc.); você pode apresentar algumas de suas próprias versões desta tarefa para torná-la mais clara. Bem, como exemplo, vamos classificar os Vingadores por altura: Ao contrário de um programa de computador, a classificação não será difícil para você, porque você será capaz de ver a imagem completa e descobrir imediatamente qual herói precisa ser movido para onde para que a classificação por altura seja concluída com sucesso. Você provavelmente já adivinhou que para classificar essa estrutura de dados em ordem crescente, basta trocar os lugares do Hulk e do Homem de Ferro:

Feito!

E isso concluirá a classificação com sucesso. Porém, o computador, ao contrário de você, é um tanto estúpido e não vê toda a estrutura de dados como um todo. Seu programa de controle só pode comparar dois valores ao mesmo tempo. Para resolver este problema, ela terá que colocar dois números em sua memória e realizar uma operação de comparação sobre eles, e depois passar para outro par de números, e assim sucessivamente até que todos os dados sejam analisados. Portanto, qualquer algoritmo de classificação pode ser bastante simplificado na forma de três etapas:

• Compare dois elementos;
• Troque ou copie um deles;
• Vá para o próximo elemento;

Algoritmos diferentes podem realizar essas operações de maneiras diferentes, mas passaremos a considerar como funciona a classificação por bolha.

Algoritmo de classificação por bolha

A classificação por bolhas é considerada a mais simples, mas antes de descrever esse algoritmo, vamos imaginar como você classificaria os Vingadores por altura se pudesse, como uma máquina, comparar apenas dois heróis entre si em um período de tempo. Provavelmente, você faria (o mais ideal) da seguinte maneira:

• Você passa para o elemento zero do nosso array (Viúva Negra);
• Compare o elemento zero (Viúva Negra) com o primeiro (Hulk);
• Se o elemento na posição zero for maior, você os troca;
• Caso contrário, se o elemento na posição zero for menor, você os deixa em seus lugares;
• Mova-se para uma posição à direita e repita a comparação (compare o Hulk com o Capitão)

Depois de percorrer toda a lista de uma só vez com esse algoritmo, a classificação não será concluída completamente. Mas, por outro lado, o maior elemento da lista será movido para a posição mais à direita. Isso sempre acontecerá, pois assim que você encontrar o elemento maior, você mudará constantemente de lugar até movê-lo até o final. Ou seja, assim que o programa “encontrar” o Hulk no array, ele o moverá ainda mais para o final da lista: É por isso que esse algoritmo é chamado de classificação por bolha, porque como resultado de sua operação, o maior elemento da lista estará no topo da matriz e todos os elementos menores serão deslocados uma posição para a esquerda: Para completar a classificação, você precisará retornar ao início do array e repetir novamente as cinco etapas descritas acima, movendo novamente da esquerda para a direita, comparando e movendo os elementos conforme necessário. Mas desta vez você precisa parar o algoritmo um elemento antes do final do array, pois já sabemos que o maior elemento (Hulk) está absolutamente na posição mais à direita: Portanto o programa deve ter dois loops. Para maior clareza, antes de prosseguirmos com a revisão do código do programa, você pode ver uma visualização de como funciona o bubble sort neste link: Visualização de como funciona o bubble sort

Implementação de classificação por bolha em Java

Para demonstrar como funciona a classificação em Java, aqui está o código do programa:

• cria um array de 5 elementos;
• carrega nele a ascensão dos vingadores;
• exibe o conteúdo da matriz;
• implementa classificação por bolha;
• exibe novamente a matriz classificada.

Você pode visualizar o código abaixo e até mesmo baixá-lo em seu IDE IntelliJ favorito . Será analisado a seguir:

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

Apesar dos comentários detalhados no código, fornecemos uma descrição de alguns dos métodos apresentados no programa. Os principais métodos que realizam o trabalho principal do programa são escritos na classe ArrayBubble. A classe contém um construtor e vários métodos:

• into– método de inserção de elementos em um array;
• printer– exibe o conteúdo do array linha por linha;

• toSwap– reorganiza os elementos, se necessário. Para isso, é utilizada uma variável temporária dummy, na qual é escrito o valor do primeiro número, e no lugar do primeiro número é escrito o valor do segundo número. O conteúdo da variável temporária é então gravado no segundo número. Esta é uma técnica padrão para trocar dois elementos;

  e finalmente o método principal:

• bubbleSorter– que faz o trabalho principal e classifica os dados armazenados no array, iremos apresentá-los separadamente novamente:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Outer loop
          for (int in = 0; in < out; in++){       //Inner loop
              if(a[in] > a[in + 1])               //If the order of the elements is wrong
                  toSwap(in, in + 1);             // call the swapping method
          }
      }
  }

Aqui você deve prestar atenção a dois contadores: externo oute interno in. O contador externoout começa a enumerar os valores a partir do final da matriz e diminui gradualmente em um a cada nova passagem. outA cada nova passagem, a variável é deslocada ainda mais para a esquerda para não afetar os valores já ordenados no lado direito do array. O contador internoin começa a enumerar valores desde o início da matriz e aumenta gradualmente em um a cada nova passagem. O aumento inocorre até atingir out(o último elemento analisado na passagem atual). O loop interno incompara duas células adjacentes ine in+1. Se inum número maior for armazenado em que in+1, então o método é chamado toSwap, que troca os lugares desses dois números.

Conclusão

O algoritmo de classificação por bolha é um dos mais lentos. Se a matriz consistir em N elementos, então N-1 comparações serão realizadas na primeira passagem, N-2 na segunda, depois N-3, etc. Ou seja, será feito o número total de passadas: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Assim, ao ordenar, o algoritmo realiza comparações de cerca de 0,5x(N ^2). Para N = 5, o número de comparações será de aproximadamente 10, para N = 10 o número de comparações aumentará para 45. Assim, à medida que o número de elementos aumenta, a complexidade da classificação aumenta significativamente: A velocidade do algoritmo é afetada não apenas pelo número de passagens, mas também pelo número de permutações que precisam ser feitas. Para dados aleatórios, o número de permutações é em média (N^2)/4, que é cerca de metade do número de passagens. No entanto, no pior caso, o número de permutações também pode ser N^2/2 - este é o caso se os dados forem inicialmente classificados na ordem inversa. Apesar de se tratar de um algoritmo de ordenação bastante lento, é muito importante conhecer e compreender como funciona e, como mencionado anteriormente, é a base para algoritmos mais complexos. Jgd!