Algoritmo de Selección

Este algoritmo de ordenamiento también es sencillo. Consiste en lo siguiente:

• Buscas el elemento más pequeño de la lista.
• Lo intercambias con el elemento ubicado en la primera posición de la lista.
• Buscas el segundo elemento más pequeño de la lista.
• Lo intercambias con el elemento que ocupa la segunda posición en la lista.
• Repites este proceso hasta que hayas ordenado toda la lista.

Análisis del algoritmo.

Estabilidad: se tiene dos registros con claves iguales, el que ocupe la posición más baja será el primero que sea identificado como menor. Es decir que será el primero en ser desplazado. El segundo registro será el menor en el siguiente ciclo y quedará en la posición adyacente. Por lo tanto se mantendrá el orden relativo. Lo que podría hacerlo inestable sería que el ciclo que busca el elemento menor revisara la lista desde la última posición hacia atrás. ¿Qué opinas tú? Yo digo que es estable, pero para hacerle caso al libro (el autor debe sabe más que yo ¿cierto?:-)) vamos a decir que no es estable.
Requerimientos de Memoria: Al igual que el ordenamiento burbuja, este algoritmo sólo necesita una variable adicional para realizar los intercambios.
Tiempo de Ejecución: El ciclo externo se ejecuta n veces para una lista de n elementos. Cada búsqueda requiere comparar todos los elementos no clasificados. Luego la complejidad es O(n2). Este algoritmo presenta un comportamiento constante independiente del orden de los datos. Luego la complejidad promedio es también O(n2).

Ventajas:

• Fácil implementación.
• No requiere memoria adicional.
• Realiza pocos intercambios.
• Rendimiento constante: poca diferencia entre el peor y el mejor caso.

Desventajas:

• Lento.
• Realiza numerosas comparaciones.

Un ejemplo
Vamos a ordenar la siguiente lista (la misma del ejemplo anterior :-) ):
4 - 3 - 5 - 2 - 1
Comenzamos buscando el elemento menor entre la primera y última posición. Es el 1. Lo intercambiamos con el 4 y la lista queda así:
1 - 3 - 5 - 2 - 4
Ahora buscamos el menor elemento entre la segunda y la última posición. Es el 2. Lo intercambiamos con el elemento en la segunda posición, es decir el 3. La lista queda así:
1 - 2 - 5 - 3 - 4
Buscamos el menor elemento entre la tercera posición (sí, adivinaste :-D) y la última. Es el 3, que intercambiamos con el 5:
1 - 2 - 3 - 5 - 4
El menor elemento entre la cuarta y quinta posición es el 4, que intercambiamos con el 5:
1 - 2 - 3 - 4 - 5
[+/-] Ejemplo...