Ordenamiento de datos por el método burbuja
Uno de los usos más comunes de las estructuras de datos es el almacenamiento de diversos valores que deben ser ordenados después. En ésta entrada te platico sobre el método de ordenamiento burbuja o bubble sort por su nombre en inglés.
Métodos de ordenamiento
Los métodos de ordenamiento son algoritmos cuyo objetivo es colocar los elementos de una lista en una secuencia ordenada, lo que generalmente implicará intercambiar la posición de los datos en la estructura de almacenamiento.
El orden que generalmente se utiliza es el numérico, pero también puede utilizarse el lexicográfico, que se aplica principalmente a cadenas de caracteres.
La importancia de seleccionar el método de ordenamiento adecuado es relevante puesto que se busca que el algoritmo provea una solución eficiente que genere el menor de los costos de procesamiento.
Orígenes del método burbuja.
Aunque existen mejores algoritmos de ordenamiento, el bubble-sort es un algoritmo suficientemente bueno como para ser un primer acercamiento al estudio de los métodos de ordenamiento.
No se conoce a ciencia cierta el autor de éste método, pero parece ser que la primera referencia a este algoritmo es de Edward H. Friend, en su publicación: Sorting on Electronic Computer Systems, aunque no se le da el nombre de bubble sort, sino más bien se le conoce como “Sorting by Exchange” o “Ordenamiento por Intercambio”.
En la actualidad sabemos que el nombre de burbuja es debido a que los números más pequeños “suben” como burbujas hacia la superficie (observa la figura 1) y los más grandes (o pesados) terminan hundiéndose, es decir, se acomodan hacia la parte final de la estructura de datos.
Se considera que éste método no es el más eficiente para ordenar una lista grande de elementos, pero sí es fácil de entender y adecuado para que los programadores que inician trabajen con arreglos de datos.
El algoritmo de ordenamiento burbuja.
Este algoritmo utiliza lo que yo llamo una “pasada”, es decir, un recorrido completo a través del arreglo a ordenar. Se comparan los datos que se encuentran en las casillas adyacentes (por ejemplo, el de la casilla 0 y el de la casilla 1) y se cambian de orden si es necesario. Así se continúa hasta recorrer todo el arreglo.
Sin embargo, una pasada no garantiza que los datos queden ordenados, por lo que es necesario realizar varias pasadas hasta que se termine con una en la que se detecte que no se hicieron cambios, lo cual indica que todos los datos están por fin en el orden deseado.
En la figura 2 te muestro el algoritmo del bubble sort:
Considerando este algoritmo, a continuación te muestro la primer pasada para ordenar el arreglo de números enteros [12, 4, 25, 6, 15, 2]:
Como puedes apreciar, después de la primera pasada, el arreglo es [4, 12, 6, 15, 2, 25], y claramente aún no está ordenado. Por lo que se requiere realizar más pasadas del algoritmo hasta que suceda una pasada sin cambios, lo que garantizaría que el arreglo esté ordenado.
En la figura 3 te muestro cómo se desarrollarían las pasadas siguientes hasta llegar a una pasada sin cambios. Esto genera que la bandera noCambios se ponga a falso, y garantiza que el arreglo ya esté ordenado.
Si observas la figura 3, llegarás a la conclusión que este algoritmo no es el mejor para ordenar grandes volúmenes de datos. Siempre va a requerir una pasada de más, en la que no se den cambios, para garantizar que el arreglo ha quedado ordenado.
A continuación te presento el código en Java para este algoritmo:
public static int[] bubbleSort( int[] datos ){
int auxiliar;
boolean noCambios;
do {
noCambios = false;
for ( int i = 0; i < datos.length-1; i++){
if ( datos[i] > datos[i+1]){
auxiliar = datos[i];
datos[i] = datos[i+1];
datos[i+1] = auxiliar;
noCambios = true;
}
}
System.out.println("Pasada: ");
imprimirDatos(datos);
} while ( noCambios == true );
return datos;
}Una mejora a este algoritmo involucra reducir el encabezado del ciclo for, y en lugar de realizar el recorrido de la primera a la última posición del arreglo, disminuir el límite superior en 1 para cada pasada , considerando que en cada recorrido se garantiza que un número queda en su lugar. Esto cambia el algoritmo de la siguiente forma:
public static int[] bubbleSort( int[] datos ){
int auxiliar;
boolean noCambios;
int pasada = 0;
do {
noCambios = false;
for ( int i = 0; i < (datos.length-1)-pasada; i++){
if ( datos[i] > datos[i+1]){
auxiliar = datos[i];
datos[i] = datos[i+1];
datos[i+1] = auxiliar;
noCambios = true;
}
}
pasada += 1;
System.out.println("Pasada: ");
imprimirDatos(datos);
} while ( noCambios == true );
return datos;
}
Es momento de concluir esta entrada. Espero que la información que te presenté te sea de utilidad. Déjame un comentario si tienes dudas, y no olvides compartir en tus redes sociales.
¡Hasta la próxima entrada!
