Página 3 de 5
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.
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.
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(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.
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.
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.
|
Comentarios
Suscripción de noticias RSS para comentarios de esta entrada.