- Comparadas
- Mínimo hasta ahora
- Intercambiadas
- En su sitio
Ordenamiento por selección
El ordenamiento por selección construye la lista ordenada desde el principio. Cada pasada recorre los valores que aún no están ordenados, recuerda el menor y lo lleva con un intercambio a la primera posición sin ordenar. Reproduce la ordenación a cualquier velocidad, o avanza de comparación en comparación, y sigue los contadores de comparaciones, intercambios y pasadas. Pulsa Reproducir para ver la ordenación, o Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto. Los recuadros cuentan comparaciones, intercambios y pasadas. Elige cuántas barras hay, cómo empiezan, o escribe tus propios números. Con el tablero seleccionado, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.
Cómo funciona
- Elige cuántas barras hay y cómo empiezan: aleatorias, casi ordenadas, invertidas o con pocos valores distintos. O escribe tus propios números.
- Pulsa Reproducir, o usa Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto de la ordenación.
- Observa cómo cambia el menor valor hasta ahora durante el recorrido, y el intercambio que lo coloca en su sitio al final de cada pasada.
Cómo funciona el ordenamiento por selección
Mira todos los valores de la lista y recuerda el menor. Intercámbialo con el primer valor: la primera posición ya es definitiva. Luego haz lo mismo con el resto de la lista, empezando una posición más adelante. Tras n − 1 pasadas todos los valores están en su sitio, y el último lo está por descarte.
Muchas comparaciones, pocos intercambios
El recorrido nunca se detiene antes, porque solo después de mirar todos los valores restantes puede saber cuál es el menor. Así que el ordenamiento por selección hace exactamente n(n − 1)/2 comparaciones para n valores, tanto si la lista está ordenada como invertida o aleatoria. A cambio, hace como máximo n − 1 intercambios, uno por pasada. Por eso es una opción razonable cuando mover un valor cuesta mucho más que comparar dos.
Preguntas frecuentes
¿Cómo funciona el ordenamiento por selección?
Selecciona una y otra vez el menor valor aún sin ordenar y lo lleva con un intercambio a la primera posición sin ordenar. Tras la pasada k, las primeras k posiciones contienen los k menores valores en orden.
¿Cuántas comparaciones e intercambios hace el ordenamiento por selección?
Siempre n(n − 1)/2 comparaciones para n valores: 45 para 10 valores, 780 para 40. El número de intercambios es como máximo n − 1, uno por pasada, y menos cuando el menor valor ya está en su sitio.
¿Por qué una lista ordenada tarda lo mismo que una invertida?
Porque cada pasada debe mirar todos los valores restantes para estar segura de haber encontrado el menor. A diferencia del ordenamiento de burbuja y del ordenamiento por inserción, el ordenamiento por selección no puede saber por sus comparaciones que la lista ya está ordenada.
¿Es estable el ordenamiento por selección?
No en esta forma habitual. Un intercambio puede llevar un valor más allá de otro igual: en 2, 2, 1 el primer 2 se intercambia con el 1 y acaba detrás del segundo 2. Una versión que desplaza los valores en lugar de intercambiarlos es estable, a costa de más movimientos.
¿Se envían mis números a algún sitio?
No. La ordenación se ejecuta en tu navegador, y tus últimos ajustes se guardan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor