Bubble Sort y Cocktail Shaker Sort en JavaScript

En este tutorial, implementaremos y optimizaremos Bubble Sort y Cocktail Shaker Sort en JavaScript con ejemplos. También realizaremos un análisis Big O.

Introducción

Bubble Sort, a veces también conocido como Sinking Sort, es uno de los algoritmos de clasificación más conocidos. Por lo general, es 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 bajo rendimiento 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. Esta es la razón por la cual 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 - Clasificación de coctelera en un intento de optimizarla.

Clasificación por burbujas {#clasificación por burbujas}

Bubble Sort es un algoritmo de clasificación de tipo de comparación. Esto significa que compara elementos individuales dentro de la colección durante el tiempo de ejecución. Según el tipo de datos y el 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. Comenzando desde el comienzo de la colección que queremos ordenar: 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 se ordenan todos los elementos de la colección. Veamos una representación visual de cómo funciona Bubble Sort:

bubble sort visualization gif

Echando un vistazo al elemento con el valor de 8, podemos verlo "burbujeando" desde el comienzo de la matriz hasta su lugar adecuado. De ahí viene el nombre de "Bubble Sort".

Implementación de clasificación por burbujas

Ahora que hemos repasado la idea detrás de Bubble Sort, podemos comenzar con la implementación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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 bucle for, 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 bucle for que compara el elemento con su elemento adyacente, cambiándolos si es necesario.

Finalmente, devolvemos la matriz ordenada. Vamos a llenar una matriz y ordenarla:

1
2
3
let inputArr = [5,1,4,2,8];
bubbleSort(inputArr);
console.log(inputArr);

Ejecutar este código producirá:

1
(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, ya que 5 < 8

Segunda iteración:

[1, 4, 2, 5, 8] -> [1, 4, 2, 5, 8] - Sin cambios, ya que 1 < 4
[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, ya que 5 < 8

La matriz se ordena en dos iteraciones, sin embargo, nuestro algoritmo continuará ejecutándose n veces, comparando todos los elementos una y otra vez. Esto se debe a que le hemos dicho que itere inputArr.length veces.

Bubble Sort es ineficiente en sí mismo, especialmente con una falla como esta. 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 a través de un indicador booleano. Cada vez que intercambiamos cualquier elemento, se establece en true:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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 terminemos de iterar a través de la matriz y no se hayan realizado intercambios, el bucle while dejará de repetirse y se devolverá la matriz.

Rellenemos la matriz de nuevo y ordenémosla:

1
2
3
let inputArr = [5,1,4,2,8];
bubbleSort(inputArr);
console.log(inputArr);

Este código da como resultado:

1
[1, 2, 4, 5, 8]

Una cosa que vale la pena señalar es que con la primera iteración terminada, el elemento más grande se ubicará al final de la matriz. La siguiente iteración colocará el segundo elemento más grande antes del más grande, y así sucesivamente.

Esto 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 iteración k-ésima, solo necesitamos echar un vistazo a las iteraciones n-k+1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
}

Rellenemos la matriz de nuevo y ordenémosla:

1
2
3
let inputArr = [5,1,4,2,8];
bubbleSort(inputArr);
console.log(inputArr);

Este código da como resultado:

1
(5) [1, 2, 4, 5, 8]

Clasificación de coctelera frente a clasificación de burbujas

Otra optimización de Bubble Sort es su variante derivada llamada Cocktail Shaker Sort, también conocida como Bidireccional Bubble Sort o simplemente Cocktail Sort.

Este algoritmo amplía Bubble Sort al operar en dos direcciones. En lugar de ir de principio a fin y repetir eso, va de principio a fin, y luego de fin a comienzo de nuevo, en una sola iteración completa. Efectivamente, logra duplicar el 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 intercambios posibles por iteración se vuelve cada vez más pequeño, lo que le da un rendimiento ligeramente mejor.

Avancemos e implementemos el algoritmo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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 clasificación por burbuja regular. Aunque, después de que pasamos hacia adelante, 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.

Si no verificamos los intercambios en el segundo paso, 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, ya que 5 < 8
[1, 4, 2, 5, 8] -> [1, 4, 2, 5, 8] - Sin cambios, ya que 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 se ordena en 1 iteración, a diferencia de las 2 iteraciones de Bubble Sort. Cocktail Sort hizo esto con 7 comparaciones, mientras que Bubble Sort lo hizo con 8. Esto no es mucho a esta escala, aunque con números más grandes, veremos mejoras en el rendimiento.

Por lo general, 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 "The Art of Computer Programming":

Pero ninguno de estos refinamientos conduce a un algoritmo mejor que la inserción directa [es decir, ordenación por inserción]; y ya sabemos que la inserción directa no es adecuada para N grandes. [...]

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.

Complejidad y comparación del tiempo

Dado que nuestra matriz contiene n elementos, Bubble Sort realiza comparaciones O(n), n veces. Esto nos lleva a un tiempo de ejecución total de O(n^2^) - 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).

Teóricamente, 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 la función integrada console.time(), podemos comparar el tiempo que lleva ejecutar el código en matrices de diferentes longitudes:

1
2
3
console.time('bubble');
bubbleSort(inputArr);
console.timeEnd('bubble');

Haremos esto para matrices de tamaño 100, 1 000 y 10 000:


Número de elementos Bubble Sort no optimizado Bubble Sort con una bandera 'booleana' Bubble Sort con n-k+1 iteraciones Cocktail Shaker Sort 100 2 ms 1 ms 1 ms 1 ms 1000 8ms 6ms 1ms 1ms 10 000 402ms 383ms 2ms 1ms


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(n^2^), y solo puede ejecutarse en su tiempo de ejecución en el mejor de los casos de O(n) cuando la matriz ya está ordenada.

Su complejidad espacial es O(1), que es genial. Desafortunadamente, eso no es suficiente para compensar la terrible complejidad del tiempo.

Incluso entre los algoritmos de ordenación simples O(n^2^), la ordenación por inserción o la ordenació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 los cursos de introducción a la informática.