Sorteo de burbujas con Java

La clasificación de burbujas es el algoritmo de clasificación más simple: suponga que hay elementos seguidos que no están ordenados. La clasificación de burbujas escanea la fila desde la izquierda, intercambiando cualquier par de elementos adyacentes que no estén en el orden correcto. Este escaneo de toda la fila se repite repetidamente hasta que se ordene toda la fila. Si la clasificación es ascender, entonces el par adyacente se cambia para hacer que el elemento a la izquierda sea menos que el elemento a la derecha. Si la clasificación está descendiendo, entonces el par adyacente se cambia para hacer que el elemento de la izquierda sea más grande que el elemento a la derecha.

Ilustración de clasificación de burbujas sin código

Considere la siguiente lista de filas sin clasificar de los caracteres del alfabeto:

P W E R T Y U I O P

Esta lista se ordenará en orden ascendente de la siguiente manera. En el primer escaneo, Q y W se comparan; Q es menor que W, por lo que no hay intercambio. Aún así, en el primer escaneo, se comparan W y E; E es menor que w, por lo que hay intercambio. El nuevo tercer elemento, W, se compara con R; R es menor que w, por lo que hay intercambio. El nuevo cuarto elemento, W, se compara con T; T es menor que w, por lo que hay intercambio. El nuevo quinto elemento, W, se compara con y; W es menos que y, y no hay intercambio. Aún así, en el primer escaneo, Y se compara con U; Es menos que y, por lo que hay intercambio. El nuevo séptimo elemento, y, se compara con I; Yo es menos que y, y hay intercambio. El nuevo octavo elemento, y, se compara con O; O es menos que y, y hay intercambio. El nuevo noveno elemento, y, se compara con P; P es menor que y, y hay intercambio. El primer escaneo termina allí. El resultado para el primer escaneo es,

Q e r t w u i o p y

Observe que el elemento más grande es al final después del primer escaneo. El escaneo de todos los diez elementos resultantes, y posible intercambio, se repite una vez más para tener:

E r q t u i o p w y

Observe que el siguiente elemento más grande es el último elemento de último pero uno, y no había necesidad de compararlo con el último elemento, por lo que no se habría desperdiciado un pequeño tiempo. El escaneo de todos los diez elementos resultantes, y posible intercambio, se repite una vez más para tener:

E q r t i o p u w y

Observe que el tercer elemento más grande hacia el final ahora está en la tercera posición desde el final, y no había necesidad de compararlo con los dos últimos elementos, y no es necesario comparar los dos últimos elementos, por lo que algunos pequeños tiempos. no habría sido perdido. El escaneo de todos los diez elementos resultantes, y posible intercambio, se repite una vez más para tener:

E q r i o p t u w y

Observe que el cuarto elemento más grande hacia el final ahora está en la cuarta posición desde el final, y no había necesidad de compararlo con los últimos tres elementos, y no es necesario comparar los últimos tres elementos, por lo que algún tiempo no lo haría. han sido desperdiciados. El escaneo de todos los diez elementos resultantes, y posible intercambio, se repite una vez más para tener:

E q i o p r t u w y

Observe que el quinto elemento más grande hacia el final ahora está en la quinta posición desde el final, y no había necesidad de compararlo con los últimos cuatro elementos, y no es necesario comparar los últimos cuatro elementos, por lo que el tiempo no habría tenido estado perdido. El escaneo de todos los diez elementos resultantes, y posible intercambio, se repite nuevamente para tener:

E i o p q r t u w y

El resto de los resultados de escaneo son los siguientes:

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 no se ha realizado una clasificación para estos últimos cuatro resultados.

El reverso de todos los algoritmos anteriores se puede hacer para que desciende.

Optimización de la clasificación de burbujas

De la definición básica de clasificación de burbujas, si hay n elementos, entonces habrá n escaneos completos. Un escaneo es una iteración. Entonces, los diez elementos anteriores significan diez iteraciones completas. La duración total de tiempo para burbujear una lista de ordenar una lista (matriz) se puede reducir para muchas listas no organizadas. Esto implica estrategias de clasificación de burbujas. Bubble Sort está optimizado con dos estrategias.

Primera estrategia de optimización

Observe de lo anterior que, después de la primera iteración completa, el elemento más grande es al final, y sería una pérdida de tiempo acceder a él en la segunda iteración. Después de la segunda iteración, los dos últimos elementos están en sus posiciones correctas, y no se debe perder el tiempo accediendo a ellos en la tercera iteración. Esto significa que la segunda iteración debería terminar en N-1. Después de la tercera iteración, los últimos tres elementos están en sus posiciones correctas, y no se debe perder el tiempo accediendo a ellos en la cuarta iteración. Esto significa que la tercera iteración debería terminar en N-2. Después de la cuarta iteración, los últimos cuatro elementos están en sus posiciones correctas, y no se debe perder el tiempo accediendo a ellos en la quinta iteración. Esto significa que la cuarta iteración debería terminar en N-3. Esto continúa.

De la definición básica del tipo de burbujas, la iteración debe hacerse n veces. Si el contador para las n iteraciones está en i, entonces la iteración debe acceder a los elementos n - i para evitar perder el tiempo al final de la matriz; y con yo comenzando desde 0. Por lo tanto, tiene que haber dos java para los bucles: el bucle externo itera n veces, y el bucle interno itera n-i tiempos, para los elementos de la matriz, para cada una de las n tiempos. Iterando una matriz n - i Times es la primera estrategia.

Segunda estrategia de optimización

¿Debería el bucle de for-boop externo realmente itere n veces?? ¿Debería el bucle de for-for-for-bool para la lista anterior iterar 10 veces?? - No, porque sus últimas cuatro iteraciones no cambiarían nada (no hace ninguna ordenación). Esto significa que la lista se ha ordenado tan pronto como se detecta; El bucle exterior debe romperse, por lo que la clasificación debe detenerse. Esto ahorrará más tiempo. Esto se puede lograr teniendo una variable booleana para el circuito externo, que permanecería falso en el bucle interno cuando se detengan el intercambio.

Código Java para clasificación de burbujas

La siguiente clase tiene el método para hacer la clasificación:

Clase Aclass
Bubblesort estático vacío (char arr [])
int n = arr.longitud;
booleano intercambiado = falso;
para (int i = 0; i < N; i++)
intercambiado = falso;
para (int j = 1; j < N - i; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
arr [j - 1] = temp;
intercambiado = verdadero;


if (swapped == falso) ruptura;

Tenga en cuenta la condición de while, "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.

Una clase principal adecuada para esto es:

clase pública THECLASS
public static void main (string [] args)
char ar [] = 'q', 'w', 'e', ​​'r', 't', 'y', 'u', 'i', 'o', 'p';
Una clase.Bubblesort (AR);
para (int i = 0; iSistema.afuera.imprimir (ar [i]); Sistema.afuera.imprimir(' ');

Sistema.afuera.println ();

La matriz se pasa por referencia al método bubblesort () en una clase diferente. Entonces su contenido se modifica. La salida es:

E i o p q r t u w y

Conclusión

Clasificación de burbujas intercambiando elementos adyacentes desde el principio hasta el final de la lista. Este procedimiento se repite una y otra vez hasta que toda la lista esté completamente ordenada. La clasificación es ascendente o descendente. La clasificación de burbujas debe optimizarse, como se explicó anteriormente.