Bubble classy with java

Bubble Sort é o algoritmo de classificação mais simples: suponha que haja elementos seguidos que não são classificados. Bubble Sort digitaliza a linha da esquerda, trocando qualquer par adjacente de elementos que não estejam na ordem correta. Esta varredura de toda a linha é repetida repetidamente até que toda a linha seja classificada. Se a classificação for ascendente, o par adjacente é trocado para tornar o elemento à esquerda menos que o elemento à direita. Se a classificação deve descer, o par adjacente é trocado para tornar o elemento à esquerda maior que o elemento à direita.

Ilustração de classificação de bolhas sem código

Considere a seguinte lista de caracteres de caracteres do alfabeto:

Q W E R T Y U I O P

Esta lista será classificada em ordem ascendente da seguinte maneira. Na primeira varredura, Q e W são comparados; Q é menor que w, então não há como trocar. Ainda assim, na primeira varredura, W e E são comparados; E é menor que W, então há trocas. O novo terceiro elemento, W, é comparado com r; R é menor que w, então há trocando. O novo quarto elemento, W, é comparado com T; T é menor que w, então há trocando. O novo quinto elemento, W, é comparado com Y; W é menor que y, e não há como trocar. Ainda assim, na primeira varredura, Y é comparado com u; Você é menor que y, então há trocando. O novo sétimo elemento, Y, é comparado com I; Eu sou menos que Y, e há trocando. O novo oitavo elemento, Y, é comparado com O; O é menor que y, e há trocando. O novo nono elemento, Y, é comparado com P; P é menor que Y, e há troca. A primeira varredura termina aí. O resultado da primeira varredura é,

Q e r t w u i o p y

Observe que o maior elemento está no final após a primeira varredura. A varredura de todos os dez elementos resultantes e a troca possível é repetida mais uma vez para ter:

E r q t u i o p w y

Observe que o próximo maior elemento é agora o último elemento, mas um, e não havia necessidade de compará-lo com o último elemento, então um pequeno tempo não teria sido desperdiçado. A varredura de todos os dez elementos resultantes e a troca possível é repetida mais uma vez para ter:

E q r t i o p u w y

Observe que o terceiro maior elemento para o final está agora na terceira posição do final, e não havia necessidade de compará-lo com os dois últimos elementos, e não há necessidade de comparar os dois últimos elementos, e então alguns pequenos tempo não teria sido desperdiçado. A varredura de todos os dez elementos resultantes e a troca possível é repetida mais uma vez para ter:

E q r i o p t u w y

Observe que o quarto maior elemento no final está agora na quarta posição do final, e não havia necessidade de compará -lo com os últimos três elementos, e não há necessidade de comparar os três últimos elementos foram desperdiçados. A varredura de todos os dez elementos resultantes e a troca possível é repetida mais uma vez para ter:

E q i o p r t u w y

Observe que o quinto maior elemento no final está agora na quinta posição desde o final, e não havia necessidade de compará -lo com os últimos quatro elementos, e não há necessidade de comparar os quatro últimos elementos, e assim o tempo não teria foi desperdiçado. A varredura de todos os dez elementos resultantes e a troca possível é repetida novamente para ter:

E i o p q r t u w y

O restante dos resultados da varredura é o seguinte:

E i o p q r t u w y
E i o p q r t u w y
E i o p q r t u w y
E i o p q r t u w y

Observe que nenhuma classificação ocorreu para esses últimos quatro resultados.

O inverso de todos os algoritmos acima pode ser feito para classificar.

Otimizando o tipo de bolha

A partir da definição básica de tipo de bolha, se houver n elementos, haverá n verificações completas. Uma varredura é uma iteração. Então, os dez elementos acima significam dez iterações completas. O tempo total de tempo para a Bubble classificar uma lista (matriz) pode ser reduzida para muitas listas não classificadas. Isso envolve estratégias de classificação de bolhas. O tipo de bolha é otimizado com duas estratégias.

Primeira estratégia de otimização

Observe do exposto que, após a primeira iteração completa, o maior elemento é no final, e seria uma perda de tempo acessando -a na segunda iteração. Após a segunda iteração, os dois últimos elementos estão em suas posições certas, e o tempo não deve ser desperdiçado acessando -os na terceira iteração. Isso significa que a segunda iteração deve terminar em N-1. Após a terceira iteração, os três últimos elementos estão em suas posições certas, e o tempo não deve ser desperdiçado acessando -os na quarta iteração. Isso significa que a terceira iteração deve terminar em N-2. Após a quarta iteração, os últimos quatro elementos estão em suas posições certas, e o tempo não deve ser desperdiçado acessando -os na quinta iteração. Isso significa que a quarta iteração deve terminar em N-3. Isso continua.

A partir da definição básica de tipo de bolha, a iteração deve ser feita n vezes. Se o balcão das nirerações estiver em I, a iteração deve acessar os elementos n - i para evitar perder tempo no final da matriz; E com eu começando de 0. Portanto, tem que haver dois loops java: o loop externo iterado n vezes, e o interior do loop itera n-i tempos, para os elementos da matriz, para cada uma das n vezes. Iterando uma matriz n - i times é a primeira estratégia.

Segunda estratégia de otimização

O loop externo deve realmente iterar n vezes? O loop externo deve ser o loop da lista acima 10 vezes? - Não, porque suas últimas quatro iterações não mudariam nada (não faz nenhuma classificação). Isso significa que a lista foi classificada assim que for detectada; O loop externo deve quebrar, então a classificação deve parar. Isso vai economizar mais tempo. Isso pode ser alcançado com uma variável booleana para o loop externo, que permaneceria falsa no loop interno quando a troca de parar de ocorrer.

Código Java para Corrente de Bubble

A aula a seguir tem o método para fazer a classificação:

classe Aclass
estático vazio bubblesort (char arr [])
int n = arr.comprimento;
booleano trocado = false;
para (int i = 0; i < N; i++)
troca = false;
for (int j = 1; j; j < N - i; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
arr [j - 1] = temp;
trocado = true;


if (trocado == false) quebra;

Observe a condição enquanto condiciona “J < N - i;” for the inner for-loop, for the first strategy. Note the use of the boolean variable in the outer for-loop and the inner for-loop for the second strategy.

Uma classe principal adequada para isso é:

classe pública theClass
public static void main (string [] args)
char ar [] = 'q', 'w', 'e', ​​'r', 't', 'y', 'u', 'i', 'o', 'p';
Uma aula.Bubblesort (AR);
para (int i = 0; iSistema.fora.impressão (ar [i]); Sistema.fora.imprimir(' ');

Sistema.fora.println ();

A matriz é passada por referência ao método bubblesort () em uma classe diferente. Portanto, seu conteúdo é modificado. A saída é:

E i o p q r t u w y

Conclusão

Classificações de bolhas trocando elementos adjacentes do início ao final da lista. Este procedimento é repetido repetidamente até que toda a lista seja completamente classificada. A classificação está ascendente ou descendente. O tipo de bolha deve ser otimizado, conforme explicado acima.