Clasificaci贸n de burbujas y clasificaci贸n de coctelera en JavaScript

    Introducci贸n

    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:

    [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, 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.

    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 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.

    Si 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

    1002ms1 ms1 ms1 ms
    10008 ms6ms1 ms1 ms
    10000402ms383ms2ms1 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.

    Su 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.

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *