Ordenar por selección en JavaScript

En este tutorial, hablaremos sobre la idea detrás de Selection Sort, la implementaremos con ejemplos y analizaremos su complejidad temporal. Además, lo compararemos con algoritmos similares.

Introducción

Selection Sort 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 usar estructuras de datos auxiliares y que la entrada es anulada por la salida (algoritmo en el lugar).

Además, durante su ejecución, solo lee los elementos de la lista a través de una sola operación de comparación abstracta, generalmente un operador "menor que o igual a" (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 temprano 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 Selection Sort y la implementaremos en JavaScript.

Después de eso, analizaremos su complejidad temporal y la compararemos con otros algoritmos de clasificación. Finalmente, discutiremos cuándo se puede usar, así como cuándo se debe evitar.

Clasificación de selección

Este algoritmo divide la matriz de entrada en dos sublistas: una sublista ordenada y sin clasificar. La lista ordenada se encuentra al comienzo de la colección y todos los elementos a la derecha del último elemento ordenado se consideran sin ordenar.

Inicialmente, la lista ordenada está vacía, mientras que el resto de la colección no está ordenada. La ordenación por selección recorre la sublista no ordenada y encuentra el elemento más pequeño o el más grande.

Luego, el elemento se intercambia con el elemento más a la izquierda de la sublista no ordenada. 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 ordenar 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 iteración k-ésima, se garantiza que los primeros k elementos de la matriz o lista se ordenarán.

Veamos esta representación visual de cómo funciona la clasificación por selección en la matriz de:

1
 5, 2, 4, 6, 1, 3

selection sort visualization

Implementación de clasificación de 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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 el subarreglo no ordenado. Si el número más pequeño no es el primero en el subarreglo sin ordenar (no está ya en su lugar), lo intercambiamos con el primer elemento del subarreglo sin ordenar.

Sin verificar si el elemento más pequeño ya es el primer elemento del subarreglo no ordenado, estaríamos realizando intercambios innecesarios.

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

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

La salida de este código será:

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

Complejidad del tiempo {#complejidad del tiempo}

La complejidad temporal de Selection Sort no es difícil de analizar.

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

Por lo tanto, el número total de comparaciones será (n-2) + (n-1) + ...+ 1, que suma n(n-1)/2 = (n^2^- n)/2. Esto nos lleva a un tiempo de ejecución de O(n^2^).

O(n^2^) es una complejidad de tiempo bastante mala para un algoritmo de clasificación. Al clasificar una colección, usaría algoritmos de clasificació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(n^2^), por lo que verificar si la matriz o la lista está ordenada o no también es realmente ineficiente.

Por otro lado, cuando se compara con otros algoritmos de complejidad temporal cuadrática como Ordenamiento de burbuja, Selection Sort se mantiene bastante bien, superando a Bubble Sort y sus variantes, así como Gnome Sort.

Sin embargo, la clasificación por inserción puede ser más rápida que la clasificación por selección en caso de que la colección esté casi ordenada. Y Insertion Sort es prácticamente invicto con colecciones cortas.

Variantes de clasificación de selección

Aunque el mejor, el peor y el desempeño promedio de este algoritmo son O(n^2^), 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. ¡Era, de hecho, una base para algunos algoritmos de clasificación muy utilizados y eficientes!

Quizás la variante más famosa es Heap Sort, que utiliza internamente una estructura de datos heap 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 total de ejecución de O(n^2) a O(nlogn), lo que se considera bueno para clasificar algoritmos.

Otra variante es BidirectionaL Selection Sort, similar a cómo Bubble Sort tiene una contraparte bidireccional. A veces se le conoce como Clasificación de cócteles (de nuevo, similar a la Clasificación de coctelera de Bubble), y hace el mismo trabajo en un ~25 % menos de comparaciones.

Conclusión

Selection Sort es un algoritmo de clasificación fundamental y simple, por lo tanto, ineficiente. Sirvió como base para algunos de los algoritmos ampliamente utilizados y adoptados y no se usa muy a menudo en la industria del desarrollo.

Sin embargo, si la colección de entrada es pequeña, la ordenación por selección es una mejor opción que la ordenación rápida o la ordenación por combinación. Pero, de nuevo, la ordenación por inserción ha demostrado ser más efectiva 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.