2 Ordenamiento por Selección.

1. Descripción.

Este algoritmo 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.

2. Pseudocódigo en C.

    1. for (i=0; i<TAM - 1; i++)
    2.      pos_men = Menor(lista, TAM, i);
    3.      temp = lista[i];
    4.      lista[i] = lista [pos_men];
    5.      lista [pos_men] = temp;
 

Nota: Menor(lista, TAM, i) es una función que busca el menor elemento entre las posiciones i y TAM-1. La búsqueda es lineal (elemento por elemento). No lo incluyo en el pseudocódigo porque es bastante simple.

3. 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

¡Y terminamos! Ya tenemos nuestra lista ordenada. ¿Fue fácil no?

4. Análisis del algoritmo.

• Estabilidad: Aquí discrepo con un libro de la bibliografía que dice que no es estable. Yo lo veo así: si tengo 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(n²). Este algoritmo presenta un comportamiento constante independiente del orden de los datos. Luego la complejidad promedio es también O(n²).

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.

Este es un algoritmo lento. No obstante, ya que sólo realiza un intercambio en cada ejecución del ciclo externo, puede ser una buena opción para listas con registros grandes y claves pequeñas. Si miras el programa de demostración notarás que es el más rápido en la parte gráfica (por lo menos en un PC lento y con una tarjeta gráfica mala como el mío x-|). La razón es que es mucho más lento dibujar las barras que comparar sus largos (el desplazamiento es más costoso que la comparación), por lo que en este caso especial puede vencer a algoritmos como Quicksort.

Bien, ya terminamos con éste. Otra vez te recomiendo que hagas un programa y trates de implementar este algoritmo, de preferencia sin mirar el código ni el pseudocódigo otra vez.