Ordenamiento por selección

El ordenamiento por selección ordena una lista como mucha gente ordena las cartas de una mano: busca la menor, ponla primero y luego busca la menor del resto. Hace muchas comparaciones pero muy pocos intercambios, y su tiempo de ejecución apenas depende del orden de la lista.

Barras de distintas alturas ordenándose, con la parte ordenada a la izquierda, la menor barra restante resaltada y una flecha que muestra cómo se intercambia hasta su sitio
Barras de distintas alturas ordenándose, con la parte ordenada a la izquierda, la menor barra restante resaltada y una flecha que muestra cómo se intercambia hasta su sitio

La idea

Divide la lista en una parte ordenada a la izquierda, vacía al principio, y una parte sin ordenar a la derecha. Recorre la parte sin ordenar y recuerda dónde está su menor valor. Intercambia ese valor con el primer valor sin ordenar: la parte ordenada ha crecido en uno. Repite hasta que solo quede un valor, que tiene que ser el mayor.

Un ejemplo

Toma 5, 1, 4, 2, 8. La primera pasada recorre los cinco valores, encuentra el 1 como menor y lo intercambia con el 5: 1, 5, 4, 2, 8. La segunda pasada recorre 5, 4, 2, 8, encuentra el 2 y lo intercambia con el 5: 1, 2, 4, 5, 8. La tercera pasada encuentra el 4 ya en su sitio, y la cuarta encuentra el 5 ya en su sitio, así que nada se mueve. Son 4 + 3 + 2 + 1 = 10 comparaciones y solo 2 intercambios. El ordenamiento de burbuja necesita 4 intercambios con la misma lista.

Siempre el mismo número de comparaciones

Para estar seguro de qué valor es el menor, el recorrido tiene que mirar todos los valores que quedan. La pasada 1 hace n − 1 comparaciones, la pasada 2 hace n − 2, y así hasta 1, lo que suma n(n − 1)/2. Este número no depende de la lista: una lista ordenada cuesta exactamente tantas comparaciones como una invertida. El ordenamiento por selección no tiene parada anticipada, porque un recorrido que encuentra el menor valor ya delante no ha aprendido nada sobre el resto.

Pocos intercambios

Cada pasada hace como máximo un intercambio, así que el ordenamiento por selección nunca hace más de n − 1 intercambios, y se salta el intercambio cuando el menor valor ya está en su sitio. El ordenamiento de burbuja y el de inserción hacen tantos intercambios como pares desordenados haya, lo que puede llegar a unos n²/2. Cuando escribir un valor es mucho más caro que leer dos, por ejemplo en una memoria que se desgasta con cada escritura, el bajo número de intercambios es una ventaja.

No es estable

Un ordenamiento es estable cuando los valores iguales mantienen su orden original. El ordenamiento por selección no lo es, porque un intercambio a larga distancia puede llevar un valor más allá de otro igual. En 2, 2, 1 la primera pasada intercambia el primer 2 con el 1, lo que da 1, 2, 2 con los dos 2 ahora en orden inverso. Una versión que desplaza los valores intermedios en lugar de intercambiar es estable, pero mueve muchos más valores.

Pruébalo

Abre la aplicación y pulsa Reproducir, o pulsa Paso para avanzar de comparación en comparación. El valor que se revisa está resaltado, el menor valor hasta ahora tiene su propio color, y cada pasada termina con un intercambio hacia la parte ordenada de la izquierda. Prueba una lista ordenada y una invertida: las comparaciones salen iguales, solo cambian los intercambios.

Preguntas frecuentes

¿Cuál es la complejidad temporal del ordenamiento por selección?

O(n²) en todos los casos: exactamente n(n − 1)/2 comparaciones para n valores, sea cual sea su orden. Hace como máximo n − 1 intercambios y solo necesita O(1) de memoria adicional.

¿Qué diferencia hay entre el ordenamiento por selección y el de burbuja?

El ordenamiento de burbuja intercambia vecinos sobre la marcha y puede parar antes cuando una pasada no hace intercambios. El ordenamiento por selección solo recuerda dónde está el menor valor y hace un intercambio al final de cada pasada. El de selección hace menos intercambios; el de burbuja es más rápido con listas casi ordenadas.

¿Es estable el ordenamiento por selección?

No. Un intercambio puede mover un valor más allá de otro valor igual, así que los valores iguales pueden cambiar de orden. Se puede hacer estable desplazando los valores en lugar de intercambiarlos, lo que cuesta más movimientos.

¿Qué relación tiene el heapsort con el ordenamiento por selección?

El heapsort es un ordenamiento por selección con una forma más rápida de encontrar el siguiente valor: guarda la parte sin ordenar en un montículo, así que cada selección tarda unos log n pasos en lugar de un recorrido completo. Eso baja el total a O(n log n).

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Prueba el ordenamiento por selección