Introducción
Contenido
Algo así como es un aspecto crítico de la digestión de datos. Para nosotros, amigos, es mucho más natural ordenar las cosas que tienen algo en común, como la fecha de publicación, el orden alfabético, los artículos por autor, de menor a mayor, etc.
Esto hace que los datos sean mucho más fáciles de entender, ya que están conectados lógicamente en lugar de dispersos.
La clasificación humana es intuitiva y simple y, por lo tanto, a menudo ineficaz. Por lo general, no trabajamos con más de dos características que queremos ordenar. Las computadoras son capaces de almacenar grandes cantidades de datos y ubicaciones de elementos en su memoria, lo que les permite ordenar colecciones de una manera que los humanos no podrían, sin mencionar la velocidad de acceso / movimiento de los elementos.
Ordenamiento de burbuja
Bubble Sort es, en la mayoría de los casos, el primer algoritmo de clasificación que encontrará cualquier entusiasta de la informática. Es el algoritmo de clasificación más simple e intuitivo, que es una de las principales razones por las que se enseña a nuevos programadores / estudiantes.
Funciona intercambiando elementos adyacentes, según criterio de mando. Por ejemplo, si queremos ordenar los elementos de la colección del más pequeño al más grande, si el primer elemento es más grande que el segundo, se intercambian. Este simple intercambio se repite con índices adyacentes hasta que finalmente se ordena la colección.
La condición de salida del algoritmo es cuando recorremos toda la colección sin intercambiar un solo elemento, lo que significa que está completamente ordenado.
Te puede interesar:El diseño del generador de patrones en JavaAquí hay una demostración visual de cómo funciona la clasificación de burbujas:
Como puede ver, el nombre en sí proviene de la ilusión visual de elementos «burbujeantes» hacia donde se necesitan. Si sigue una función en particular, diga, 8 – puede notar que está «burbujeando» en el lugar correcto en este ejemplo.
Implementación
Con una breve descripción general de la teoría detrás de la clasificación de burbujas fuera del camino, apliquémosla clasificando dos tipos diferentes de colecciones. Primero, ordenaremos un conjunto simple y luego ordenaremos ArrayList con un objeto personalizado y un compareTo() método.
Ordenar matrices
Comenzamos ordenando un conjunto de números enteros:
public void bubbleSort(int[] array) {
boolean sorted = false;
int temp;
while (!sorted) {
sorted = true;
for (int i = 0; i < array.length - 1; i++) {
if (a[i] > a[i+1]) {
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
sorted = false;
}
}
}
}
El es sorted se usa una bandera para indicar si la edición está editada o no. Si no hay razón para cambiar ningún elemento o reemplazar a[i] siempre menos que a[i+1] en una iteración separada, el sorted una bandera nunca se reinicia false.
Porque se queda true, la matriz se ordena y salimos del bucle.
Pase este código:
Te puede interesar:Java: busque subcadena en la cadenaint[] array = new int[]{5, 6, 7, 2, 4, 1, 7};
bubbleSort(array);
System.out.println(Arrays.toString(array));
El resultado será:
[1, 2, 4, 5, 6, 7, 7]
Nota: Dado que las matrices se tratan como objetos en Java, sí void el tipo de retorno es completamente válido al ordenar matrices, y el contenido no se copia al pie de la letra cuando se usa como argumento. En este caso, la edición está «en vigor».
Ordenar listas de matrices
Un escenario más común sería ordenar ArrayList poblado por objetos no numéricos. Estos pueden ser empleados, resultados de bases de datos, usuarios, etc. Dado que no sabemos de antemano cómo resolver estas cosas, la persona que llama tendrá que proporcionarlo a través del comapreTo() método.
Definamos una clase para nuestros elementos que se almacenarán en una colección:
public class Element {
private int id;
public Element(int id) {
this.id = id;
}
// Getters and setters
public int compareTo(Element element) {
int res = 0;
if (this.id < element.getId()) {
res =- 1;
}
if (this.id > element.getId()) {
res = 1;
}
return res;
}
}
Es una clase muy simple con un área: id. Nosotros tambien podemos @Override un toString() método si queremos imprimir los resultados, pero en aras de la nitidez, no lo hagamos aquí y allá getId() método en su lugar.
Para clasificar ArrayLists, dado que estamos trabajando con objetos, es un poco diferente a ordenar arreglos simples de valores primitivos, ya que no podemos usar operadores relativos.
Ahora nuestro compareTo() el método compara el idsy devoluciones -1 Si el id el elemento actual es más pequeño que el elemento que estamos comparando, 1 Si el id del elemento de corriente superior, o 0 si son idénticos.
De hecho, puede aplicar la funcionalidad comparativa de la forma que desee.
Ahora volvamos a aplicar Bubble Sort:
public void bubbleSortArrayList(List<Element> list) {
Element temp;
boolean sorted = false;
while (!sorted) {
sorted = true;
for (int i = 0; i < list.size()-1; i++) {
if (list.get(i).compareTo(list.get(i + 1)) > 0) {
temp = list.get(i);
list.set(i, list.get(i + 1));
list.set(i + 1, temp);
sorted = false;
}
}
}
}
Este es un código bastante simple, casi idéntico al código del ejemplo con matrices, utilizando los métodos proporcionados por List interfaz.
Ahora, hagamos una población ArrayList con algunos elementos:
List<Element> list = new ArrayList<>();
// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
list.add(new Element(i));
}
// Move the elements to a random order
Collections.shuffle(list);
Y podemos ordenarlo:
// Print list before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));
// Sort the list
bubbleSort.bubbleSortArrayList(list);
System.out.println();
// Print sorted list
list.forEach(e -> System.out.print(e.getId() + ", "));
Como era de esperar, el resultado es:
17, 13, 14, 5, 15, 22, 24, 7, 3, 9, 21, 10, 1, 11, 18, 20, 12, 8, 4, 19, 0, 23, 16, 2, 6,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
API de colecciones
Una gran ventaja de la API de colecciones que se inicia con Java 8 son los métodos de asistente que le permiten ordenar las colecciones de forma rápida y sencilla. Solo necesitamos el Comparable interfaz para los elementos que queremos ordenar más tarde.
Cambiamos nuestro Element clase para que el Comparable interfaz:
public class Element implements Comparable<Element> {
private int id;
// Constructor, getters and setters
@Override
public int compareTo(Element element) {
int res = 0;
if (this.id < element.getId()) {
res =- 1;
}
if (this.id > element.getId()) {
res = 1;
}
return res;
}
}
Como puede ver, el Element la clase es casi la misma que antes. Esta vez, ponemos el Comparable interfaz y anularla compareTo() método con la misma lógica que antes.
Ahora podemos simplemente llamar Collections.sort() en nuestra lista:
List<Element> list = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
list.add(new Element(i));
}
Collections.shuffle(list);
// Print shuffled list
list.forEach(e -> System.out.print(e.getId() + ", "));
// Sort the list
Collections.sort(list);
System.out.println();
// Print sorted list
list.forEach(e -> System.out.print(e.getId() + ", "));
El es sort() utiliza el método de la API de clasificación rápida de colecciones para ordenar la colección dada. Esto tiene enormes ventajas de rendimiento en comparación con Bubble Sort, pero lo guardaremos para otro artículo.
Complejidad del tiempo
O (n ^ 2) es la media temporal (media y peor) de Clasificación de burbujas. Esto es, desde el punto de vista realista, terrible para un algoritmo de clasificación.
Si bien es terrible, así es como funcionó el algoritmo al recolectar 10,000 objetos en una colección:
List<Element> list = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
list.add(new Element(i));
}
Collections.shuffle(list);
// Print shuffled collection
list.forEach(e -> System.out.print(e.getId() + ", "));
long startTime = System.nanoTime();
bubbleSort.bubbleSortArrayList(list);
long endTime = System.nanoTime();
// Print sorted collection
list.forEach(e -> System.out.print(e.getId() + ", "));
System.out.println();
// Print runtime in nanoseconds
System.out.println("Bubble Sort runtime: " + (endTime - startTime));
Y aquí están los resultados en segundos después de ejecutar 10 veces:
Te puede interesar:Anulación de método en JavaHora (s) de clasificación de burbujas
| Primer intento | 0.5885202 |
| Segunda ejecución | 0,6647364 |
| La tercera carrera | 0.5748066 |
| Cuarta carrera | 0.5266222 |
| Quinta carrera | 0.522961 |
| La sexta carrera | 0.5033268 |
| Séptima carrera | 0.5044489 |
| Ocho carreras | 0,6409187 |
| La novena carrera | 0.6021427 |
| La décima carrera | 0,694294 |
Con un tiempo de ejecución medio de ~ 0,5 s para 10,000 objetos, ¿realmente necesitará algoritmos que funcionen mejor? La mayoría de las veces, no realmente, a menos que tenga una aplicación de alta carga que requiera un tiempo de respuesta rápido.
Si está haciendo comparaciones más complejas que solo hacer una comparación idsy tienen una colección enorme, mucho más que esta; sí, si se usa un algoritmo avanzado con una complejidad de tiempo mucho mejor, afectará en gran medida su rendimiento.
Como referencia, el sort() Ordene el método de la API de colecciones de este mismo conjunto de 10,000 elementos en solo 0.01s de manera consistente. Por lo tanto, incluso si no hay una necesidad real de ordenar sus colecciones más rápido que 0.5s, ahorrará tiempo mientras codifica y mejora su aplicación usando un clasificador integrado provisto por la API de Colecciones.
Conclusión
Bubble Sort es, en la mayoría de los casos, el primer algoritmo de clasificación que encontrará cualquier entusiasta de la informática. Es el algoritmo de clasificación más simple e intuitivo y es una de las principales razones por las que se enseña temprano.
Hemos visto que este sencillo algoritmo de clasificación funciona intercambiando elementos adyacentes, de acuerdo con criterios de comando específicos. Por ejemplo, si queremos ordenar los elementos de la colección del más pequeño al más grande, si el primer elemento es más grande que el segundo, se intercambian. Este simple intercambio se repite para índices adyacentes hasta que finalmente se ordena la colección.
Es muy eficiente y dado que los algoritmos mucho más eficientes están integrados en Java en la API de colección, le recomendamos que no utilice este algoritmo para ninguna aplicación de producción.
Te puede interesar:La anotación @Value en Spring.
