La versión simplificada del ordenamiento por cubetas no solo presenta los problemas mencionados en la sección anterior, sino que tiene un inconveniente aún más crítico: ¡consume una cantidad excesiva de espacio!
Por ejemplo, si el rango de números a ordenar está entre 0 y 2,100,000,000, necesitarías declarar 2,100,000,001 variables, es decir, algo como int a[2100000001]. Esto se debe a que necesitamos 2,100,000,001 "cubetas" para almacenar la frecuencia de cada número entre 0 y 2,100,000,000. Incluso si solo tienes 5 números para ordenar (por ejemplo, 1, 1,912,345,678, 2,100,000,000, 18,000,000 y 912,345,678), aún así necesitarías 2,100,000,001 "cubetas", ¡lo cual es un desperdicio de espacio enorme! Además, ¿qué pasaría si los números a ordenar ya no son enteros, sino decimales? Por ejemplo, ¿cómo ordenarías los números 5.56789, 2.12, 1.1, 3.123 y 4.1234 de menor a mayor?
Ahora vamos a aprender un nuevo algoritmo de ordenación: el ordenamiento por burbuja. Este algoritmo resuelve eficazmente ambos problemas.
Concepto Básico del Ordenamiento por Burbuja
La idea fundamental del ordenamiento por burbuja es: comparar elementos adyacentes e intercambiarlos si están en el orden incorrecto.
Supongamos que queremos ordenar los números [12, 35, 99, 18, 76] de mayor a menor. Esto significa que los números más pequeños deben quedar al final. Aunque parezca obvio, este punto es crucial.
Primero, comparamos el primer y segundo elemento: 12 y 35. Como 12 es menor que 35 y queremos que los números más pequeños queden al final, intercambiamos estos elementos. Después del entercambio, la secuencia es: 35, 12, 99, 18, 76.
Continuamos comparando el segundo y tercer elemento: 12 y 99. Como 12 es menor, los intercambiamos. Ahora la secuencia es: 35, 99, 12, 18, 76.
Seguimos el proceso comparando el tercer y cuarto elemento: 12 y 18. Como 12 es menor, los intercambiamos. La secuencia ahora es: 35, 99, 18, 12, 76.
Finalmente, comparamos el cuarto y quinto elemento: 12 y 76. Como 12 es menor, los intercambiamos. Después de 4 comparaciones, la secuencia es: 35, 99, 18, 76, 12.
Después de estas 4 comparaciones, observamos que el número más pequeño (12) ya está en su posición final (el último lugar). Este proceso se parece a una burbuja que se desplaza hacia atrás hasta llegar al final, de ahí el nombre "ordenamiento por burbuja".
Iteraciones del Algoritmo
Hasta ahora, solo hemos posicionado correctamente el número más pequeño de la secuencia. Cada vez que posicionamos un número en su lugar correcto, lo llamamos una "pasada" o "iteración". Ahora repetiremos el proceso para posicionar los números restantes.
Segunda pasada: Nuestro objetivo es colocar el segundo número más pequeño en su posición correcta. Comparamos el primer y segundo elemento: 35 y 99. Como 35 es menor, los intercambiamos. La secuencia ahora es: 99, 35, 18, 76, 12.
Continuamos comparando el segundo y tercer elemento: 35 y 18. Como 35 es mayor, no es necesario intercambiar. Ahora comparamos el tercer y cuarto elemento: 18 y 76. Como 18 es menor, los intercambiamos. Después de esta segunda pasada, la secuencia es: 99, 35, 76, 18, 12.
Tercera pasada: Repetimos el proceso. Después de la tercera pasada, la secuencia es: 99, 76, 35, 18, 12.
Cuarta pasada: Algunos podrían preguntar si ya está ordenado. ¡Sí, en este caso particular ya está ordenado, pero esto es solo coincidencia! Si pruebas con otros números, podría no ser el caso. ¿Puedes encontrar una secuencia donde se necesiten más pasadas?
El principio del ordenamiento por burbuja es que cada pasada solo posiciona un número. La primera pasada posiciona el número más pequeño al final, la segunda posiciona el segundo más pequeño penúltimo, y así sucesivamente. Con 5 números, necesitamos 4 pasadas para ordenar completamente la secuencia.
Implementación en Código
A continuación, presentamos una implementación del ordenamiento por burbuja en C. Esta versión ordena una lista de estudiantes por sus puntuaciones de mayor a menor.
#include <stdio.h>
// Estructura para almacenar información de los estudiantes
typedef struct {
char nombre[21];
int puntuacion;
} RegistroEstudiante;
int main() {
RegistroEstudiante lista[100], temporal;
int total, i, j;
// Leer el número de estudiantes
scanf("%d", &total);
// Leer los datos de cada estudiante
for(i = 0; i < total; i++) {
scanf("%s %d", lista[i].nombre, &lista[i].puntuacion);
}
// Ordenar por puntuación de mayor a menor usando burbuja
for(i = 0; i < total - 1; i++) {
for(j = 0; j < total - i - 1; j++) {
if(lista[j].puntuacion < lista[j+1].puntuacion) {
// Intercambiar si el actual es menor que el siguiente
temporal = lista[j];
lista[j] = lista[j+1];
lista[j+1] = temporal;
}
}
}
// Imprimir los nombres ordenados
for(i = 0; i < total; i++) {
printf("%s\n", lista[i].nombre);
}
// Limpiar el buffer de entrada
while(getchar() != '\n');
getchar();
return 0;
}</stdio.h>
Puedes probar el programa con los siguientes datos de entrada:
5
huhu 5
haha 3
xixi 5
hengheng 2
gaoshou 8
El resultado esperado es:
gaoshou
huhu
xixi
haha
hengheng
Análisis de Complejidad
La parte central del ordenamiento por burbuja es el uso de bucles anidados. Es fácil ver que la complejidad temporal del ordenamiento por burbuja es O(n²), lo que lo hace ineficiente para grandes conjuntos de datos.
El ordenamiento por burbuja ha sido estudiado desde 1956, y muchas personas han intentado mejoralro, con resultados decepcionantes. Como dijo Donald E. Knuth (ganador del Premio Turing en 1974): "El ordenamiento por burbuja, aparte de su nombre encentador y el hecho de que ha llevado a ciertos problemas teóricos interesantes, no parece tener nada que lo recomiende".
¿Podrías preguntar: ¿existen algoritmos de ordenación más eficientes? ¡Sí! En futuros artículos exploraremos algoritmos más avanzados como el ordenamiento rápido (quicksort).