El algoritmo de ordenación de burbuja es un método sencillo para ordenar una colección de elementos. Funciona iterando repetidamente a través de la lista, comparando pares de elementos adyacentes y intercambiándolos si están en el orden incorrecto. Este proceso se repite hasta que no se necesiten más intercambios, lo que indica que la lista está ordenada. En cada pasada, el elemento más grande no ordenado "burbujea" hasta su posición correcta al final de la porción no ordenada de la lista.

Funcionamiento Básico:

1. Comenzar desde el primer elemento del arreglo.
2. Comparar el elemento actual con el siguiente elemento.
3. Si el elemento actual es mayor que el siguiente, intercambiarlos.
4. Continuar este proceso hasta llegar al final del arreglo.
5. Repetir los pasos anteriores. En cada pasada completa, el siguiente elemento más grande se colocará en su posición final correcta.
6. El algoritmo termina cuando una pasada completa no produce ningún intercambio.

Implementación en Java

A continuación, se presenta una implementación básica del algoritmo de burbuja en Java:

/**
* Función auxiliar para intercambiar dos elementos en un arreglo.
* @param arr El arreglo de enteros.
* @param idx1 Índice del primer elemento a intercambiar.
* @param idx2 Índice del segundo elemento a intercambiar.
*/
private static void intercambiar(int[] arr, int idx1, int idx2) {
   int temporal = arr[idx1];
   arr[idx1] = arr[idx2];
   arr[idx2] = temporal;
}

/**
* Implementa el algoritmo de ordenación de burbuja.
* @param arr El arreglo de enteros a ordenar.
*/
public static void ordenacionBurbuja(int[] arr) {
   int n = arr.length;
   // Bucle externo para controlar las pasadas. Se necesitan n-1 pasadas en el peor caso.
   for (int i = 0; i < n - 1; i++) {
       // Bucle interno para comparar elementos adyacentes.
       // La porción ya ordenada al final (n-i-1) no necesita ser revisada.
       for (int j = 0; j < n - i - 1; j++) {
           // Si el elemento actual es mayor que el siguiente, intercambiarlos.
           if (arr[j] > arr[j + 1]) {
               intercambiar(arr, j, j + 1);
           }
       }
   }
}
 

Optimización

Se puede optimizar el algoritmo de burbuja introduciendo una bandera para detectar si se realizaron intercambios en una pasada. Si en una pasada completa no se realiza ningún intecrambio, significa que el arreglo ya está ordenado y podemos detener el proceso prematuramente.

/**
* Implementa el algoritmo de ordenación de burbuja optimizado.
* @param arr El arreglo de enteros a ordenar.
*/
public static void ordenacionBurbujaOptimizado(int[] arr) {
   int n = arr.length;
   boolean huboIntercambio;
   // Bucle externo para controlar las pasadas.
   for (int i = 0; i < n - 1; i++) {
       huboIntercambio = false; // Reiniciar la bandera al inicio de cada pasada.
       // Bucle interno para comparar elementos adyacentes.
       for (int j = 0; j < n - i - 1; j++) {
           // Si el elemento actual es mayor que el siguiente, intercambiarlos.
           if (arr[j] > arr[j + 1]) {
               intercambiar(arr, j, j + 1);
               huboIntercambio = true; // Marcar que hubo un intercambio.
           }
       }
       // Si no hubo intercambios en esta pasada, el arreglo está ordenado.
       if (!huboIntercambio) {
           break;
       }
   }
}
 

Análisis de Complejidad y Estabilidad

• Complejidad Temporal: En el peor y caso promedio, el algoritmo de burbuja realiza O(n2) comparaciones e intercambios, donde 'n' es el número de elementos. En el mejor caso (arreglo ya ordenado), con la optimización, su complejidad es O(n).
• Complejidad Espacial: El algoritmo utiliza una cantidad constante de memoria adicional (para variables temporales y la bandera), por lo que su complejidad espacial es O(1).
• Estabilidad: El algoritmo de burbuja es estable. Esto significa que si dos elementos tienen el mismo valor, su orden relativo original se mantiene después de la ordenación. Esto se debe a que solo se intercambian elementos si son estrictamente mayores, y los elementos iguales no provocan un intercambio.