Introducción
Contenido
Bubble Sort, a veces también conocido como Sinking Sort es uno de los algoritmos de clasificación más conocidos. Suele ser uno de los primeros algoritmos de clasificación con los que se encuentran los estudiantes de informática debido a su simplicidad y al hecho de que es bastante intuitivo y fácil de traducir a código.
Sin embargo, este sencillo algoritmo ha mostrado un rendimiento deficiente en problemas de la vida real. Especialmente en comparación con algoritmos más rápidos, populares y ampliamente utilizados como Quicksort o Merge Sort. Es por eso que Bubble Sort se usa principalmente como una herramienta educativa.
En este artículo, explicaremos cómo funciona Bubble Sort y lo implementaremos en JavaScript. También comprobaremos su complejidad temporal y la compararemos con otros algoritmos de clasificación.
Además, implementaremos una de sus variantes, Cocktail Shaker Sort, en un intento de optimizarlo.
Ordenamiento de burbuja
Bubble Sort es un algoritmo de clasificación de tipo comparativo. Esto significa que compara elementos individuales dentro de la colección durante el tiempo de ejecución. Dependiendo de su tipo de datos y propósito, la comparación se puede realizar mediante un operador relacional o mediante una función de comparación personalizada.
La idea detrás de Bubble Sort es bastante simple. Empezando desde el principio de la colección queremos ser ordenados – comparamos elementos dentro de un par. Si el par está en el orden deseado, no hacemos nada. Si no es así, intercambiamos los elementos que lo componen.
Esto se hace una y otra vez, hasta que todos los elementos de la colección estén ordenados. Veamos una representación visual de cómo funciona Bubble Sort:
Echando un vistazo al elemento con el valor de 8, podemos verlo «burbujear» desde el principio de la matriz hasta su lugar adecuado. De aquí proviene el nombre de «Bubble Sort».
Implementación de clasificación de burbujas
Ahora que hemos repasado la idea detrás de Bubble Sort, podemos comenzar con la implementación:
function bubbleSort(inputArr) {
let n = inputArr.length;
for(let i = 0; i < n; i++) {
for(let j = 0; j < n; j++) {
// Comparing and swapping the elements
if(inputArr[j] > inputArr[j+1]){
let t = inputArr[j];
inputArr[j] = inputArr[j+1];
inputArr[j+1] = t;
}
}
}
return inputArr;
}
La implementación es bastante intuitiva. Iteramos a través de la matriz n veces con un for bucle, donde n es la longitud de la matriz. Para cada iteración, «burbujeamos» un elemento en su lugar correcto. Esto se hace a través de otro for bucle que compara el elemento con el adyacente, cambiándolos si es necesario.
Finalmente, devolvemos la matriz ordenada. Completemos una matriz y ordenemos:
let inputArr = [5,1,4,2,8];
bubbleSort(inputArr);
console.log(inputArr);
Ejecutar este código producirá:
(5) [1, 2, 4, 5, 8]
Echemos un vistazo a cómo se hace esto con valores concretos:
Primera iteración:
[5, 1, 4, 2, 8] -> [1, 5, 4, 2, 8] – Estamos intercambiando 5 y 1, ya que 5> 1[1, 5, 4, 2, 8] -> [1, 4, 5, 2, 8] – Estamos intercambiando 5 y 4, ya que 5> 4
[1, 4, 5, 2, 8] -> [1, 4, 2, 5, 8] – Estamos intercambiando 5 y 2, ya que 5> 2
[1, 4, 2, 5, 8] -> [1, 4, 2, 5, 8] – Sin cambios, desde 5 <8
Segunda iteración:
Te puede interesar:Introducción a los servicios web de Amazon en Node.js[1, 4, 2, 5, 8] -> [1, 2, 4, 5, 8] – Estamos intercambiando 4 y 2, ya que 4> 2
[1, 2, 4, 5, 8] -> [1, 2, 4, 5, 8] – Sin cambios, ya que 4 <5
[1, 2, 4, 5, 8] -> [1, 2, 4, 5, 8] – Sin cambios, desde 5 <8
La matriz se ordena en dos iteraciones, sin embargo, nuestro algoritmo seguirá ejecutándose n veces, comparando todos los elementos una y otra vez. Esto se debe a que le hemos dicho que repita inputArr.length veces.
Bubble Sort es ineficiente en sí mismo, especialmente con un defecto como este. Sin embargo, hay dos cosas que podemos hacer para optimizarlo.
Optimizaciones
La primera optimización que podemos implementar es: terminar el algoritmo si la matriz está ordenada, es decir, no se realizan intercambios. Esto se puede hacer mediante un boolean bandera. Cada vez que intercambiamos elementos, se establece en true:
function bubbleSort(inputArr) {
let n = inputArr.length;
let sorted = false;
while (!sorted) {
sorted = true;
for(let i = 0; i < n; i++){
if(inputArr[i] > inputArr[i+1]){
let t = inputArr[i];
inputArr[i] = inputArr[i+1];
inputArr[i+1] = t;
sorted = false;
}
}
}
return inputArr;
}
Tan pronto como terminamos de iterar a través de la matriz y no se realizaron intercambios, el while El bucle dejará de repetirse y se devolverá la matriz.
Volvamos a rellenar la matriz y ordénela:
let inputArr = [5,1,4,2,8];
bubbleSort(inputArr);
console.log(inputArr);
Este código da como resultado:
[1, 2, 4, 5, 8]
Algo que vale la pena señalar es que con la primera iteración finalizada, el elemento más grande se ubicará al final de la matriz. La siguiente iteración colocará el segundo elemento más grande antes que el más grande, y así sucesivamente.
Te puede interesar:Guía de manillares: motor de plantillas para Node / JavaScriptEsto significa que con cada iteración, realmente no necesitamos mirar el último elemento, ya que sabemos que está en el lugar correcto. Por lo tanto, en la k-ésima iteración, solo necesitamos echar un vistazo a las n-k + 1 iteraciones:
function bubbleSort(inputArr) {
let n = inputArr.length;
let sorted = false;
let numOfIterations = 0;
while(!sorted) {
sorted = true;
for(let i = 0; i < n-numOfIterations+1; i++){
if(inputArr[i] > inputArr[i+1]){
let t = inputArr[i];
inputArr[i] = inputArr[i+1];
inputArr[i+1] = t;
sorted = false;
numOfIterations++;
}
}
}
return inputArr;
}
Volvamos a rellenar la matriz y ordénela:
let inputArr = [5,1,4,2,8];
bubbleSort(inputArr);
console.log(inputArr);
Este código da como resultado:
(5) [1, 2, 4, 5, 8]
Clasificación de coctelera vs clasificación de burbujas
Otra optimización de Bubble Sort es su variante derivada llamada Cocktail Shaker Sort, también conocida como Bidirectional Bubble Sort o simplemente Cocktail Sort.
Este algoritmo extiende Bubble Sort operando en dos direcciones. En lugar de ir de principio a fin, y repetir eso, va de principio a fin, y luego de un final a otro, en una sola iteración completa. Efectivamente, logra el doble del trabajo de Bubble Sort en una sola iteración completa, aunque en la práctica no suele funcionar dos veces más rápido.
Esto se debe a que tiene un recuento de comparación similar. Compara más elementos por iteración que Bubble Sort normal y duplica los intercambios por iteración. La razón por la que es más rápido es porque el rango de posibles intercambios por iteración se hace cada vez más pequeño, lo que le da un rendimiento ligeramente mejor.
Sigamos adelante e implementemos el algoritmo:
function cocktailShakerSort(inputArr) {
let n = inputArr.length;
let sorted = false;
while (!sorted) {
sorted = true;
for (let i = 0; i < n - 1; i++) {
if (inputArr[i] > inputArr[i + 1]){
let tmp = inputArr[i];
inputArr[i] = inputArr[i + 1];
inputArr[i+1] = tmp;
sorted = false;
}
}
if (sorted)
break;
sorted = true;
for (let j = n - 1; j > 0; j--) {
if (inputArr[j-1] > inputArr[j]) {
let tmp = inputArr[j];
inputArr[j] = inputArr[j + 1];
inputArr[j+1] = tmp;
sorted = false;
}
}
}
return inputArr;
}
La primera parte es la misma que la ordenación de burbujas normal. Aunque, después de avanzar, retrocedemos. Primero, verificamos si la matriz está ordenada con el pase hacia adelante anterior. Si no, retrocedemos, intercambiando si es necesario. Si no se realizan intercambios, el algoritmo finaliza y se devuelve el resultado.
Te puede interesar:Introducción a los proxies de JavaScript en ES6Si no verificamos los intercambios en la segunda pasada, tendríamos que pasar un tiempo adicional hacia adelante para verificar si la matriz está ordenada.
Echemos un vistazo al ejemplo manual de antes, esta vez con Cocktail Shaker:
[5, 1, 4, 2, 8] -> [1, 5, 4, 2, 8] – Estamos intercambiando 5 y 1, ya que 5> 1[1, 5, 4, 2, 8] -> [1, 4, 5, 2, 8] – Estamos intercambiando 5 y 4, ya que 5> 4
[1, 4, 5, 2, 8] -> [1, 4, 2, 5, 8] – Estamos intercambiando 5 y 2, ya que 5> 2
[1, 4, 2, 5, 8] -> [1, 4, 2, 5, 8] – Sin cambios, desde 5 <8
[1, 4, 2, 5, 8] -> [1, 4, 2, 5, 8] – Sin cambios, desde 5> 2
[1, 4, 2, 5, 8] -> [1, 2, 4, 5, 8] – Estamos intercambiando 4 y 2, ya que 2 <4
[1, 2, 4, 5, 8] -> [1, 2, 4, 5, 8] – Sin cambios, ya que 2> 1
Aquí, nuestra matriz está ordenada en 1 iteración, a diferencia de las 2 iteraciones de Bubble Sort. Cocktail Sort hizo esto con 7 comparaciones, mientras que Bubble Sort hizo esto con 8. Esto no es mucho en esta escala, aunque con números más grandes, veremos mejoras en el rendimiento.
Normalmente, esto da como resultado un rendimiento un 33% más rápido.
Donald E. Knuth mencionó Cocktail Shaker Sort, junto con algunas variantes similares de Bubble Sort, en su famosa monografía «El arte de la programación informática»:
Pero ninguno de estos refinamientos conduce a un algoritmo mejor que la inserción directa [that is, insertion sort]; y ya sabemos que la inserción recta no es adecuada para N. […]
En resumen, el tipo de burbuja parece no tener nada que lo recomiende, excepto un nombre pegadizo y el hecho de que conduce a algunos problemas teóricos interesantes.
Comparación y complejidad del tiempo
Dado que nuestra matriz contiene n elementos, Bubble Sort realiza O (n) comparaciones, n veces. Esto nos lleva a un tiempo de ejecución total de O (n2): promedio y peor de los casos. Esta es una complejidad de tiempo horrible para un algoritmo de clasificación.
Como referencia, los algoritmos de clasificación más comunes, como Quicksort o Merge Sort, tienen un tiempo de ejecución promedio de O (nlogn).
En teoría, Bubble Sort podría tener una complejidad O (n), si lo ejecutamos en una colección ordenada, que supera a todos los demás algoritmos excepto Insertion Sort y Cube Sort. Sin embargo, la rareza de este caso no justifica su uso en la práctica.
Usando el incorporado console.time() función, podemos comparar el tiempo que lleva ejecutar el código en matrices de diferentes longitudes:
console.time('bubble');
bubbleSort(inputArr);
console.timeEnd('bubble');
Haremos esto para matrices de tamaño 100, 1000 y 10000:
Número de elementos Clasificación de burbujas no optimizada Clasificación de burbujas con un indicador ‘booleano’ Clasificación de burbujas con n-k + 1 iteraciones Clasificación de coctelera
| 100 | 2ms | 1 ms | 1 ms | 1 ms |
| 1000 | 8 ms | 6ms | 1 ms | 1 ms |
| 10000 | 402ms | 383ms | 2ms | 1 ms |
Lo que es evidente aquí es cuán ineficiente es la primera implementación en comparación con variantes como Cocktail Shaker.
Conclusión
Aunque Bubble Sort es muy intuitivo y fácil de entender e implementar, es muy poco práctico para resolver la mayoría de los problemas.
Tiene un tiempo de ejecución promedio y en el peor de los casos de O (n2), y solo puede ejecutarse en su mejor tiempo de ejecución de O (n) cuando la matriz ya está ordenada.
Te puede interesar:Expresiones de función invocadas inmediatamente de JavaScriptSu complejidad espacial es O (1), lo cual es genial. Desafortunadamente, eso no es suficiente para compensar la terrible complejidad del tiempo.
Incluso entre los algoritmos simples de clasificación O (n2), la clasificación por inserción o la clasificación por selección suelen ser considerablemente más eficientes.
Debido a su simplicidad, Bubble Sort se usa a menudo como una introducción a los algoritmos de clasificación en cursos de introducción a la informática.
