Métodos de ordenamiento.

...

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 se incluyo en el pseudocódigo porque es bastante simple.

3. Un ejemplo.

Se ordenará la siguiente lista:

4 - 3 - 5 - 2 - 1

Se comienza buscando el elemento menor entre la primera y última posición. Es el 1. Se intercambia con el 4 y la lista quedará así:

1 - 3 - 5 - 2 - 4

Ahora se busca el menor elemento entre la segunda y la última posición. Es el 2. Se intercambia con el elemento en la segunda posición, es decir el 3. La lista queda así:

1 - 2 - 5 - 3 - 4

Luego se busca el menor elemento entre la tercera posición y la última. Es el 3, que se intercambia con el 5:

1 - 2 - 3 - 5 - 4

El menor elemento entre la cuarta y quinta posición es el 4, se intercambia con el 5:

1 - 2 - 3 - 4 - 5

Y se finaliza el programa. La lista está ordenada.

4. Análisis del algoritmo.

- Estabilidad: 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 esO(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.

+ Ordenamiento por Inserción.

1. Descripción.

El método de "inserción" está basado en la técnica que utilizan los jugadores de cartas para odernar sus cartas. El jugador va insertando cada una de las cartas en la posición correspondiente.

Se considera una parte de la lista ya ordenada, ubicando cada elemento y colocándolo en el lugar que corresponde tomándo en cuenta su valor, como se muestra en la siguiente imágen:

[pic 2]

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

j

Entero

Contador

temp

El mismo que los elementos de la lista

Para realizar los intercambios

1. for (i=1; i

2. temp = lista[i];

3. j = i - 1;

4. while ((lista[j] > temp) && (j >= 0))

5. lista [j+1] = lista[j];

6. j--;

7. lista [j+1] = temp;

3. Análisis del algoritmo.

- Estabilidad: Este algoritmo nunca intercambia registros con claves iguales. Por lo tanto es estable.

- Requerimientos de Memoria: Una variable adicional para realizar los intercambios.

- Tiempo de Ejecución: Para una lista de n elementos el ciclo externo se ejecuta n-1 veces. El ciclo interno se ejecuta como máximo una vez en la primera iteración, 2 veces en la segunda, 3 veces en la tercera, etc. Esto produce una complejidad O (n2).

Ventajas:

- Fácil implementación.

- Requerimientos mínimos de memoria.

Desventajas:

- Lento.

- Realiza numerosas comparaciones.

Este es un algoritmo lento, pero puede ser de utilidad para listas que están ordenadas o semiordenadas, porque en ese caso realiza muy pocos desplazamientos.