Análisis y Diseño de Algoritmos

Prof: Ing. Victor Garro

Asistente: Marco Elizondo Vargas

ORDENAMIENTOS

Ordenamiento Seleccion

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.

Pseudocódigo en C.

Tabla de variables
Nombre	Tipo	Uso
lista	Cualquiera	Lista a ordenar
TAM	Constante entera	Tamaño de la lista
i	Entero	Contador
pos_men	Entero	Posición del menor elemento de la lista
temp	El mismo que los elementos de la lista	Para realizar los intercambios

    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.

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

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.