Orden de selecci贸n en JavaScript

     

    Introducci贸n

    La clasificaci贸n por selecci贸n es uno de los algoritmos de clasificaci贸n m谩s simples e intuitivos. Es un algoritmo de comparaci贸n inestable e in situ.

    Esto significa que transforma la colecci贸n de entrada sin utilizar estructuras de datos auxiliares y que la entrada es anulada por la salida (algoritmo in situ).

    Adem谩s, durante su ejecuci贸n, solo lee los elementos de la lista a trav茅s de una 煤nica operaci贸n de comparaci贸n abstracta, generalmente un operador “menor o igual que” (algoritmo de comparaci贸n).

    Finalmente, el orden de los elementos duplicados no se conserva despu茅s de la clasificaci贸n (algoritmo inestable).

    Por lo general, se ense帽a al principio en la mayor铆a de los cursos de Ciencias de la Computaci贸n, dado que es muy f谩cil de entender y traducir a c贸digo. A pesar de su complejidad de tiempo cuadr谩tico, tiene ventajas de rendimiento sobre algunos algoritmos de clasificaci贸n m谩s complejos, como Quicksort o Merge Sort, en algunos casos espec铆ficos.

    En este art铆culo, explicaremos la idea detr谩s de la ordenaci贸n por selecci贸n y la implementaremos en JavaScript.

    Despu茅s de eso, analizaremos su complejidad de tiempo y la compararemos con otros algoritmos de clasificaci贸n. Finalmente, discutiremos cu谩ndo se puede usar, as铆 como cu谩ndo se debe evitar.

    Orden de selecci贸n

    Este algoritmo divide la matriz de entrada en dos sublistas: una sublista ordenada y no ordenada. La lista ordenada se encuentra al comienzo de la colecci贸n y todos los elementos a la derecha del elemento ordenado final se consideran no clasificados.

    Inicialmente, la lista ordenada est谩 vac铆a, mientras que el resto de la colecci贸n no est谩 ordenada. La clasificaci贸n por selecci贸n recorre la sublista sin clasificar y encuentra el elemento m谩s peque帽o o m谩s grande.

    A continuaci贸n, el elemento se intercambia con el elemento m谩s a la izquierda de la sublista sin clasificar. Luego, la sublista ordenada se expande para incluir ese elemento.

    Esto se repite, encontrando el elemento adecuado, intercambi谩ndolo con el elemento m谩s a la izquierda de la lista sin clasificar y expandiendo la lista ordenada para abarcarlo.

    Despu茅s de cada iteraci贸n, se debe verificar un elemento menos, hasta que se ordene toda la matriz o lista. En otras palabras, despu茅s de la k-茅sima iteraci贸n, se garantiza que los primeros k elementos de la matriz o lista estar谩n ordenados.

    Veamos esta representaci贸n visual de c贸mo funciona el ordenamiento por selecci贸n en la matriz de:

     5, 2, 4, 6, 1, 3
    

    Implementaci贸n de clasificaci贸n por selecci贸n

    Ahora que hemos superado la idea detr谩s de Selection Sort y su representaci贸n visual, podemos pasar a la implementaci贸n del algoritmo en JavaScript:

    function selectionSort(inputArr) { 
        let n = inputArr.length;
            
        for(let i = 0; i < n; i++) {
            // Finding the smallest number in the subarray
            let min = i;
            for(let j = i+1; j < n; j++){
                if(inputArr[j] < inputArr[min]) {
                    min=j; 
                }
             }
             if (min != i) {
                 // Swapping the elements
                 let tmp = inputArr[i]; 
                 inputArr[i] = inputArr[min];
                 inputArr[min] = tmp;      
            }
        }
        return inputArr;
    }
    

    Estamos iterando a trav茅s de toda la matriz de entrada, y para cada elemento de la matriz, encontramos el n煤mero m谩s peque帽o en la submatriz sin clasificar. Si el n煤mero m谩s peque帽o no es el primero en el subarreglo sin clasificar (a煤n no est谩 en su lugar), lo intercambiamos con el primer elemento del subarreglo sin clasificar.

    Sin comprobar si el elemento m谩s peque帽o ya es el primer elemento del subarreglo sin clasificar, estar铆amos realizando intercambios innecesarios.

    Ahora, agreguemos la matriz de entrada e invoquemos nuestra funci贸n:

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

    La salida de este c贸digo ser谩:

    (6) [1, 2, 3, 4, 5, 6]
    

    Complejidad del tiempo

    La complejidad temporal de la clasificaci贸n por selecci贸n no es dif铆cil de analizar.

    En la primera iteraci贸n, a lo largo de la matriz de n elementos, hacemos n-1 comparaciones y potencialmente un intercambio. En la segunda iteraci贸n, haremos n-2 comparaciones, y as铆 sucesivamente.

    Por lo tanto, el n煤mero total de comparaciones ser谩 (n-2) + (n-1) + … + 1, lo que suma n (n-1) / 2 = (n2-n) / 2. Esto nos lleva a un tiempo de ejecuci贸n de O (n2).

    O (n2) es una complejidad de tiempo bastante mala para un algoritmo de clasificaci贸n. Al ordenar una colecci贸n, usar铆a algoritmos de ordenaci贸n m谩s r谩pidos como Quicksort o Merge Sort con una complejidad de tiempo de O (nlogn).

    El rendimiento en el mejor de los casos de la ordenaci贸n por selecci贸n tambi茅n es O (n2), por lo que comprobar si la matriz o la lista est谩 ordenada o no tambi茅n es realmente ineficiente.

    Por otro lado, en comparaci贸n con otros algoritmos de complejidad de tiempo cuadr谩tico como Bubble Sort, Selection Sort se mantiene bastante bien, superando a Bubble Sort y sus variantes, as铆 como Gnome Sort.

    Sin embargo, la ordenaci贸n por inserci贸n puede ser m谩s r谩pida que la ordenaci贸n por selecci贸n en caso de que la colecci贸n est茅 casi ordenada. Y Insertion Sort est谩 pr谩cticamente invicto con colecciones cortas.

    Variantes de ordenaci贸n por selecci贸n

    A pesar de que el mejor, el peor y el promedio de rendimiento de este algoritmo son O (n2), lo que lo hace bastante ineficiente, la clasificaci贸n por selecci贸n es muy importante para el desarrollo general de los algoritmos de clasificaci贸n. 隆Fue, de hecho, la base de algunos algoritmos de clasificaci贸n eficientes y muy utilizados!

    Quiz谩s la variante m谩s famosa es Heap Sort, que utiliza internamente una estructura de datos de mont贸n para almacenar elementos. El uso de montones puede acelerar la b煤squeda y eliminaci贸n de elementos a un tiempo O (logn).

    Esta es una optimizaci贸n muy beneficiosa que reduce el tiempo de ejecuci贸n total de O (n ^ 2) a O (nlogn), lo que se considera bueno para los algoritmos de clasificaci贸n.

    Otra variante es la clasificaci贸n por selecci贸n bidireccional, similar a la forma en que la clasificaci贸n por burbujas tiene una contraparte bidireccional. A veces se lo conoce como Cocktail Sort (de nuevo, similar al Cocktail Shaker Sort de Bubble) y hace el mismo trabajo en ~ 25% menos comparaciones.

    Conclusi贸n

    La clasificaci贸n por selecci贸n es un algoritmo de clasificaci贸n fundamental y simple, por lo tanto ineficaz. Sirvi贸 como base para algunos de los algoritmos ampliamente utilizados y adoptados y no se utiliza con mucha frecuencia en la industria del desarrollo.

    Sin embargo, si la colecci贸n de entrada es peque帽a, la clasificaci贸n por selecci贸n es una mejor opci贸n que la clasificaci贸n r谩pida o la clasificaci贸n por combinaci贸n. Pero, de nuevo, la ordenaci贸n por inserci贸n ha demostrado ser m谩s eficaz que la ordenaci贸n por selecci贸n en estos casos.

    En este art铆culo, repasamos la idea detr谩s de Selection Sort, la implementamos en JavaScript, exploramos su complejidad temporal y mencionamos brevemente algunas de sus variantes.

     

    Etiquetas:

    Deja una respuesta

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