Introdução ao Bubble Sort em Java
A classificação por bolhas é um dos algoritmos mais usados para classificar dados em Java. A classificação aqui é feita comparando recursivamente os números adjacentes e deslocando-os na ordem crescente ou decrescente, conforme necessário. Essa troca de elementos é feita até que todos os dígitos sejam completamente classificados na ordem necessária.
O nome "Classificação da bolha" desse algoritmo ocorre porque os elementos de uma matriz marcam caminho até o início. Vamos entender o algoritmo de classificação de bolhas tomando um exemplo.
Exemplo: considere uma matriz de números (6 1 8 5 3) que precisa ser organizada em ordem crescente.
O algoritmo de classificação de bolhas funciona em várias iterações até descobrir que todos os números estão classificados.
Iterações
Abaixo estão as iterações realizadas no Bubble Sort em Java, que são as seguintes:
Primeira Iteração
(6 1 8 5 3) - Começa comparando os dois primeiros números e desloca o número menor dos dois para a direita. Portanto, entre 6 e 1, 1 é o número menor que é deslocado para a esquerda e 6 para a direita. (1 6 8 5 3) - Em seguida, compara os dois números adjacentes deslocando uma posição para a direita. Aqui, o número 6 é menor que 8 e, portanto, a mesma ordem é mantida. (1 6 8 5 3) - Novamente, deslocando uma posição para a comparação correta ocorre entre 8 e 5. O número 5 é deslocado para a esquerda, pois é menor que 8. (1 6 5 8 3) - Aqui a comparação ocorre entre os números 8 e 3. O número 3 é deslocado para a esquerda, pois é menor que 8. (1 6 5 3 8) - Este é o resultado final do pedido após a 1ª iteração.Segunda Iteração
Como os números ainda não estão completamente em sua ordem crescente ainda, o programa segue para a segunda iteração.
(1 6 5 3 8) - Aqui a comparação começa novamente a partir dos dois primeiros dígitos do resultado da primeira iteração. Ele compara os números 1 e 6 e mantém a mesma ordem, pois 1 é menor que 6. (1 6 5 3 8) - Aqui são comparados os números 5 e 6. A mesma ordem é mantida, pois já está na ordem crescente necessária. (1 5 6 3 8) - Aqui a comparação ocorre entre os números 6 e 3. O número 3 é deslocado para a esquerda, pois é menor que 6. (1 5 3 6 8) - Os números seguintes 6 e 8 são comparados entre si. A mesma ordem é retida como na ordem esperada. (1 5 3 6 8) - Este é o resultado final após a segunda iteração. Ainda assim, podemos notar que os dígitos não estão completamente organizados em sua ordem crescente. Ainda precisamos trocar os números 5 e 3 para obter o resultado final. Portanto, o programa vai para a terceira iteração.Terceira Iteração
(1 5 3 6 8) - a terceira iteração começa comparando os dois primeiros dígitos 1 e 5. Como o pedido é o esperado, ele é mantido da mesma forma. (1 5 3 6 8) - Em seguida, os números adjacentes 3 e 5 são comparados. Como 5 é maior que 3, é deslocado para o lado direito. (1 3 5 6 8) - A iteração continua a comparar os números 5 e 6, 6 e 8. Como está na ordem necessária, ela retém a ordem. (1 3 5 6 8) - Finalmente, a iteração é interrompida quando o programa percorre a comparação de cada elemento adjacente e descobre que todos os dígitos estão na ordem crescente.Como aqui havia apenas 5 elementos de uma matriz que precisavam ser classificados, foram necessárias apenas 3 iterações no total. À medida que os elementos na matriz aumentam, a quantidade de iterações também aumenta.
Implementação de classificação de bolha usando Java
Abaixo está o código Java, que é a implementação do algoritmo de classificação Bubble. (Observe que a primeira posição de uma matriz em Java começa em 0 e continua em incrementos de 1, ou seja, matriz (0), matriz (1), matriz (2) e continua.)
Código:
import java.util.Scanner;
public class BubbleSort (
static void bubbleSort(int() arraytest) (
int n = arraytest.length; //length of the array is initialized to the integer n
int temp = 0; //A temporary variable called temp is declared as an integer and initialized to 0
for(int i=0; i < n; i++)( // first for loop performs multiple iterations
for(int j=1; j < (ni); j++)(
if(arraytest(j-1) > arraytest(j))( // if loop compares the adjacent numbers
// swaps the numbers
temp = arraytest(j-1); // assigns the greater number to temp variable
arraytest(j-1) = arraytest(j); // shifts the lesser number to the previous position
arraytest(j) = temp; // bigger number is then assigned to the right hand side
)
)
)
)
public static void main(String() args) (
int arraytest() =(23, 16, 3, 42, 75, 536, 61); // defining the values of array
System.out.println("Array Before Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++)( // for loop used to print the values of array
System.out.print(arraytest(i) + " ");
)
System.out.println();
bubbleSort(arraytest); // array elements are sorted using bubble sort function
System.out.println("Array After Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++)(
System.out.print(arraytest(i) + " "); // for loop to print output values from array
)
)
)
Resultado:
Vantagens e desvantagens do Bubble Sort em Java
Abaixo estão as diferentes vantagens e desvantagens do tipo de bolha em java:
Vantagens
- O código é muito fácil de escrever e entender. Normalmente leva apenas alguns minutos.
- A implementação também é muito fácil.
- A classificação de bolhas classifica os números e os mantém na memória, portanto, economiza muita memória.
Desvantagens
- Esse algoritmo não é adequado para grandes conjuntos de dados, pois a comparação leva muito tempo. O tempo necessário para classificar os números de entrada aumenta exponencialmente.
- O (n 2) é a complexidade média da classificação por bolhas e O (n) é a complexidade do melhor caso (o melhor caso é quando os elementos são classificados em primeiro lugar) onde n é o número de elementos.
Aplicativos em tempo real
Como a classificação por bolhas é capaz de detectar erros mínimos na classificação, é usada em gráficos de computador. Também é usado no algoritmo de preenchimento de polígono, onde os vértices que revestem o polígono precisam ser classificados.
Conclusão
Neste artigo, vimos como o algoritmo de classificação Bubble funciona e como ele pode ser implementado usando a programação Java. A classificação por bolha é um algoritmo muito estável que pode ser facilmente implementado para conjuntos de dados comparativamente pequenos. É um caso de algoritmo de comparação e é usado por iniciantes devido à sua simplicidade.
Artigos recomendados
Este é um guia para o Bubble Sort em Java. Aqui discutimos várias iterações para executar a classificação de bolhas no java e sua implementação de código, além de vantagens e desvantagens. Você também pode consultar os seguintes artigos para saber mais -
- Bubble Classificar em JavaScript
- Classificação em R
- Matrizes 3D em Java
- Matrizes em c #
- Classificação da bolha em Python