1. Introducción
En este artículo rápido, exploraremos el algoritmo Bubble Sort en detalle, centrándonos en una implementación de Java.
Este es uno de los algoritmos de clasificación más sencillos; la idea central es seguir intercambiando elementos adyacentes de una matriz si están en un orden incorrecto hasta que se clasifique la colección.
Los elementos pequeños “aparecen” en la parte superior de la lista a medida que iteramos la estructura de datos. Por lo tanto, la técnica se conoce como clasificación de burbujas.
Como la clasificación se realiza mediante intercambio, podemos decir que realiza una clasificación en el lugar.
Además, si dos elementos tienen los mismos valores, los datos resultantes conservarán su orden , lo que los convierte en una clasificación estable.
2. Metodología
Como se mencionó anteriormente, para ordenar una matriz, la iteramos mientras comparamos elementos adyacentes y los intercambiamos si es necesario. Para una matriz de tamaño n , realizamos n-1 de tales iteraciones.
Tomemos un ejemplo para entender la metodología. Nos gustaría ordenar la matriz en orden ascendente:
4 2 1 6 3 5
Comenzamos la primera iteración comparando 4 y 2; definitivamente no están en el orden correcto. El intercambio resultaría en:
[2 4] 1 6 3 5
Ahora, repitiendo lo mismo para 4 y 1:
2 [1 4] 6 3 5
Seguimos haciéndolo hasta el final:
2 1 [ 4 6] 3 5
2 1 4 [3 6] 5
2 1 4 3 [5 6]
Como podemos ver, al final de la primera iteración, obtuvimos el último elemento en el lugar que le corresponde. Ahora, todo lo que tenemos que hacer es repetir el mismo procedimiento en más iteraciones. Excepto, excluimos los elementos que ya están ordenados.
En la segunda iteración, iteraremos a través de toda la matriz excepto por el último elemento. De manera similar, para la tercera iteración, omitimos los 2 últimos elementos. En general, para la k-ésima iteración, iteramos hasta el índice nk (excluido). Al final de n-1 iteraciones, obtendremos la matriz ordenada.
Ahora que comprende la técnica, profundicemos en la implementación.
3. Implementación
Implementemos la clasificación para la matriz de ejemplo que discutimos usando el enfoque de Java 8:
void bubbleSort(Integer[] arr) { int n = arr.length; IntStream.range(0, n - 1) .flatMap(i -> IntStream.range(1, n - i)) .forEach(j -> { if (arr[j - 1] > arr[j]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } }); }Y una prueba rápida de JUnit para el algoritmo:
@Test public void whenSortedWithBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.bubbleSort(array); assertArrayEquals(array, sortedArray); }4. Complejidad y optimización
Como podemos ver, para el promedio y el peor de los casos , la complejidad del tiempo es O (n ^ 2) .
Además, la complejidad del espacio , incluso en el peor de los casos, es O (1) ya que el algoritmo de clasificación de burbujas no requiere memoria adicional y la clasificación se realiza en la matriz original.
Al analizar la solución con cuidado, podemos ver que si no se encuentran intercambios en una iteración, no es necesario que repita más .
En el caso del ejemplo discutido anteriormente, después de la segunda iteración, obtenemos:
1 2 3 4 5 6
En la tercera iteración, no necesitamos intercambiar ningún par de elementos adyacentes. Entonces podemos omitir todas las iteraciones restantes.
En el caso de una matriz ordenada, el intercambio no será necesario en la primera iteración, lo que significa que podemos detener la ejecución. Este es el mejor escenario y la complejidad temporal del algoritmo es O (n) .
Ahora, implementemos la solución optimizada.
public void optimizedBubbleSort(Integer[] arr) { int i = 0, n = arr.length; boolean swapNeeded = true; while (i < n - 1 && swapNeeded) { swapNeeded = false; for (int j = 1; j arr[j]) { int temp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = temp; swapNeeded = true; } } if(!swapNeeded) { break; } i++; } }Comprobemos la salida del algoritmo optimizado:
@Test public void givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.optimizedBubbleSort(array); assertArrayEquals(array, sortedArray); }5. Conclusión
En este tutorial, vimos cómo funciona Bubble Sort y su implementación en Java. También vimos cómo se puede optimizar. Para resumir, es un algoritmo estable in situ, con complejidad de tiempo:
- Caso peor y promedio: O (n * n), cuando la matriz está en orden inverso
- Mejor caso: O (n), cuando la matriz ya está ordenada
El algoritmo es popular en los gráficos por computadora, debido a su capacidad para detectar algunos pequeños errores en la clasificación. Por ejemplo, en una matriz casi ordenada, solo es necesario intercambiar dos elementos para obtener una matriz completamente ordenada. Bubble Sort puede corregir estos errores (es decir, ordenar esta matriz) en tiempo lineal.
Como siempre, el código para la implementación de este algoritmo se puede encontrar en GitHub.