HOWTO · JavaScript
Ordenar por selección en JavaScript
En este artículo, aprenderemos el algoritmo de clasificación por selección en JavaScript. Y usando este algoritmo, aprenderemos cómo podemos ordenar los elementos de la matriz en JavaScript con la ayuda de un ejemplo.
En esta página
El ordenamiento por selección busca repetidamente el valor más pequeño de la parte aún desordenada de un arreglo y lo coloca en la siguiente posición de la izquierda. La guía general sobre el ordenamiento por selección presenta el algoritmo; esta guía lo implementa en JavaScript y recorre sus pasadas con un arreglo concreto.
Qué hace el ordenamiento por selección
Imagina el arreglo dividido en dos regiones contiguas. La región ordenada crece desde la izquierda y la región sin ordenar ocupa el resto. Al principio, la región ordenada está vacía. En cada pasada, el algoritmo recorre la región sin ordenar, recuerda el índice de su valor más pequeño e intercambia ese valor con el primer elemento de la región. Así, la región ordenada crece una posición. Cuando queda un solo elemento fuera de ella, ese elemento ya está en la posición correcta.
El procedimiento es sencillo:
- Toma el índice sin ordenar más a la izquierda como la posición que se debe ocupar.
- Guarda ese índice en
minIndex, el candidato actual al valor más pequeño. - Compara cada elemento posterior con el candidato y actualiza
minIndexcuando encuentra un valor menor. - Intercambia el candidato con el elemento de la posición que se debe ocupar.
- Avanza una posición hacia la derecha y repite.
La variable guarda un índice, no el valor mínimo. Así, el algoritmo realiza un solo intercambio al terminar el recorrido, en lugar de mover elementos del arreglo cada vez que encuentra un candidato menor.
Implementar el ordenamiento por selección en JavaScript
Esta función ordena un arreglo de números en el propio arreglo y devuelve la misma referencia. El bucle externo elige cada posición que se debe ocupar. El bucle interno empieza una posición más adelante, por lo que busca solo en la parte sin ordenar. Al terminar ese recorrido, una variable temporal conserva el valor que se va a intercambiar.
Ejecuta este ejemplo en un entorno de JavaScript, como Node.js:
El código y las etiquetas o salidas visibles de esta sección se mantienen en inglés.
function selectionSort(array) {
for (let i = 0; i < array.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
const current = array[i];
array[i] = array[minIndex];
array[minIndex] = current;
}
return array;
}
const values = [3, 8, 2, 10, 1, 5, 7, 4, 9, 6];
console.log("Input:", values.join(", "));
console.log("Sorted:", selectionSort(values).join(", "));
Input: 3, 8, 2, 10, 1, 5, 7, 4, 9, 6
Sorted: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
La ejecución correcta muestra primero el arreglo de entrada y después el arreglo ordenado. Las etiquetas visibles del ejemplo, Input y Sorted, se mantienen en inglés. La función modifica el arreglo original y devuelve esa misma referencia; si necesitas conservar el orden inicial, crea primero una copia.
Recorrer el algoritmo con un ejemplo
Para [3, 8, 2, 10, 1, 5, 7, 4, 9, 6], el primer recorrido examina todos los elementos y encuentra 1 en el índice 4. Intercambia ese valor con el primer elemento, 3. La región ordenada ahora contiene 1, y el siguiente recorrido empieza en el índice 1.
En la pasada siguiente, el menor de los valores restantes es 2, que pasa al índice 1. La tercera pasada encuentra 3 y lo coloca en el índice 2. En la cuarta, 4 es el menor de los valores restantes y pasa al índice 3. La quinta coloca 5 en el índice 4. En todo momento, el prefijo de la izquierda está en orden ascendente y el recorrido no necesita volver a examinarlo.
Este recorrido también muestra por qué el código lleva la cuenta de minIndex: durante una pasada puede cambiar varias veces al encontrar candidatos menores, pero el intercambio no se realiza hasta que el recorrido llega al final de la región sin ordenar. Si el elemento actual ya es el mínimo, se intercambia consigo mismo y el algoritmo continúa.
Complejidad temporal y espacial
Para una entrada de n elementos, la primera pasada realiza n - 1 comparaciones, la siguiente n - 2, y las comparaciones continúan hasta llegar a una. La suma es n(n - 1) / 2, por lo que el ordenamiento por selección tarda Θ(n²) en los casos mejor, promedio y peor. Incluso si la entrada ya está ordenada, el algoritmo sigue recorriendo los valores restantes; esta implementación no detecta que podría terminar antes.
La función usa Θ(1) de espacio adicional: mantiene unos pocos índices y un valor temporal, y modifica el arreglo proporcionado en lugar de crear otro cuyo tamaño dependa de la entrada. El ordenamiento por selección realiza como máximo n − 1 pasadas de intercambio, pero esta implementación ejecuta ambas asignaciones al arreglo en cada pasada, incluso cuando se intercambia un elemento consigo mismo porque minIndex === i. Por tanto, ese límite de intercambios no significa que el código evite escrituras cuando el mínimo ya está en su posición. El número cuadrático de comparaciones también lo hace poco adecuado para colecciones grandes.
Cuándo usar el ordenamiento por selección
El ordenamiento por selección es útil para aprender cómo un algoritmo de ordenación mantiene una invariante: después de cada pasada, el prefijo izquierdo contiene los valores más pequeños en su orden definitivo. También puede ser adecuado para un arreglo pequeño cuando importa más una implementación sencilla y en el propio arreglo que la velocidad. Para código de aplicación general y entradas grandes, es preferible usar el método integrado Array.prototype.sort() de JavaScript con un comparador numérico, como (a, b) => a - b; el entorno de ejecución optimiza ese método, que conviene preferir salvo que un requisito concreto exija este algoritmo.
El ejemplo compara números mediante <. Para cadenas, objetos o registros, la regla de comparación debe corresponder a los valores que se van a ordenar; esta implementación no admite un comparador personalizado. Para probar el código, guárdalo en un archivo de JavaScript y ejecútalo con un entorno de JavaScript, o pégalo en una consola compatible.