Orden de selección en JavaScript

O

 

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.

 

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad