Java de classificação por bolha

Se você já ouviu falar de métodos de classificação em programação, provavelmente foi o algoritmo de classificação por bolhas. É um famoso. Todo programador conhece o bubble sort (ou pelo menos ouviu falar dele enquanto aprende) não porque é o melhor algoritmo de classificação do mundo, mas o mais fácil. Esse algoritmo geralmente é usado para fins de aprendizado ou você pode obtê-lo como uma tarefa em sua entrevista Java Junior. O algoritmo Java Bubble sort é muito fácil de entender, porém não é eficiente. De qualquer forma, vamos descobrir.

O que é classificação

Antes de tudo, você precisa entender o que é classificação em geral e o que podemos classificar em programas Java. Se pudermos comparar dois ou mais elementos ou objetos por qualquer um de seus atributos, isso significa que eles podem ser classificados por esse atributo. Por exemplo, números em ordem crescente ou decrescente ou palavras em ordem alfabética. Portanto, os elementos devem ser comparáveis ​​entre si. A propósito, os elementos de quê? Em Java, podemos comparar os elementos de Collections. Por exemplo, podemos classificar Array ou ArrayList de inteiros, Strings e assim por diante.

Como funciona a classificação por bolhas

Digamos que precisamos classificar um array de números inteiros em ordem crescente, ou seja, do menor para o maior número. Primeiro, percorremos todo o array e comparamos cada 2 elementos vizinhos. Se eles estiverem na ordem errada (o vizinho da esquerda é maior que o da direita), nós os trocamos. Na primeira passagem ao final aparecerá o maior elemento (se ordenarmos em ordem crescente). Você pode dizer, o maior elemento “aparece”. Essa é a razão do nome do algoritmo Bubble sort. Repetimos o primeiro passo do primeiro ao penúltimo elemento. Temos o segundo maior elemento no penúltimo lugar. E assim por diante. Podemos melhorar um pouco um algoritmo verificando se pelo menos uma troca na etapa anterior foi feita. Se não for, paramos de correr ao longo da matriz.

Exemplo de classificação de bolha

Vamos classificar o array de inteiros, aquele que você pode ver abaixo na foto. Passo 1: estamos percorrendo o array. O algoritmo começa com os dois primeiros elementos (com índices 0 e 1), 8 e 7, e verifica se eles estão na ordem correta. Obviamente, 8 > 7, então nós os trocamos. A seguir, olhamos para o segundo e terceiro elementos (índices 1 e 2), agora são 8 e 1. Pelas mesmas razões, nós os trocamos. Pela terceira vez comparamos 8 e 2 e, pelo menos, 8 e 5. Fizemos quatro trocas no total: (8, 7), (8, 1), (8, 2) e (8, 5). Um valor de 8, o maior nessa matriz, apareceu no final da lista na posição correta. O resultado da primeira etapa do funcionamento do algoritmo Bubble sort é a próxima matriz: Passo 2. Fazendo o mesmo com (7,1), (7,2) e (7,5). O 7 agora está na penúltima posição, e não precisamos compará-lo com a "cauda" da lista, ele já está classificado. O resultado da segunda etapa do funcionamento do algoritmo Bubble sort é a próxima matriz: Como você pode ver, esta matriz já está classificada. De qualquer forma, o algoritmo Bubble Sort deve continuar pelo menos mais uma vez. Etapa 3. Estamos passando pela matriz mais uma vez. Nada para trocar aqui, portanto, se estivermos usando o algoritmo Bubble Sort “aprimorado” (com verificação se pelo menos uma troca na etapa anterior foi feita), esta etapa é a última.

Código Java de classificação por bolha

Realização de Java de ordenação de bolha

Vamos criar dois métodos para Bubble sort. O primeiro, bubbleSort(int[] myArray) é plano. Ele percorre o array todas as vezes. O segundo, OptimizedBubbleSort(int myArray[]) é otimizado parando o algoritmo se o loop interno não causar nenhuma troca. O contador mostra quantas etapas você executou durante a classificação. Aqui temos a realização de Bubble sort Java:

import java.util.Arrays;

public class BubbleSortExample {

   //  Plane Bubble sort example

   public static int[] bubbleSort(int[] myArray) {

       int temp = 0;  //  temporary element for swapping
       int counter = 0;  //  element to count quantity of steps

       for (int i = 0; i < myArray.length; i++) {
           counter = i + 1;
           for (int j = 1; j < (myArray.length - i); j++) {

               if (myArray[j - 1] > myArray[j]) {
                   //  swap array’s elements using temporary element
                   temp = myArray[j - 1];
                   myArray[j - 1] = myArray[j];
                   myArray[j] = temp;
               }
           }
       }
       System.out.println("Steps quantity, non optimized = " + counter);
       return myArray;
   }
   //  An optimized version of Java Bubble Sorting

   static int[] optimizedBubbleSort(int myArray[]) {
       int temp;
       boolean swapped;
       int counter = 0;  //  element to count quantity of steps
       for (int i = 0; i < myArray.length - 1; i++) {
           counter = i + 1;
           swapped = false;
           for (int j = 0; j < myArray.length - i - 1; j++) {
               //  counter++;
               if (myArray[j] > myArray[j + 1]) {
                   //  swap arr[j] and arr[j+1]
                   temp = myArray[j];
                   myArray[j] = myArray[j + 1];
                   myArray[j + 1] = temp;
                   swapped = true;

               }
           }  //  counter = i;
           //  If there weren't elements to swap in inner loop, then break
           if (swapped == false) {

               break;

           }
       }
       System.out.println("steps quantity, optimized = " + counter);
       return myArray;
   }


   public static void main(String[] args) {
       int arr[] = {8, 7, 1, 2, 5};
       int arr1[] = {8, 7, 1, 2, 5};

       System.out.println("Array arr Before Bubble Sort");
       //  we use java.util.Arrays toString method to print the array  
 System.out.println(Arrays.toString(arr));

       System.out.println("Array arr After Bubble Sort");
       System.out.println(Arrays.toString(bubbleSort(arr)));

       System.out.println("Array arr1 Before Bubble Sort");
       System.out.println(Arrays.toString(arr1));

       System.out.println("Array arr1 After Optimized Bubble Sort");
       System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
   }
}

O resultado do trabalho do algoritmo Java Bubble sort:

Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]

Qual é a eficiência do Bubble Sort?

Bubble sort é um dos algoritmos mais fáceis de implementar, mas não é eficiente. Requer um par de loops aninhados. Mesmo em uma versão otimizada do algoritmo no pior caso (cada elemento do conjunto de dados está na ordem inversa à desejada), o loop externo itera uma vez para cada um dos n elementos do conjunto de dados. O loop interno itera n vezes o pela primeira vez, ( n-1 ) pela segunda e assim por diante. Portanto, para obter todos os n , elementos classificados, os loops precisam ser executados n*(n-1)/2 vezes. Ele chama O(n ² )complexidade de tempo e significa que o algoritmo faz cerca de 500.000 comparações para 1.000 elementos de uma matriz. No entanto, o algoritmo de classificação de bolhas é bastante eficaz no uso de memória (a complexidade da memória é O(n) ) e é realmente bom para pequenos conjuntos de dados quase classificados.