Algoritmos de ordenación no recursivos (página 2)

Algoritmo Selección

El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición y así excluirlo de la lista. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo.

Es un algoritmo lento, a pesar que sólo realiza un intercambio en cada ejecución del ciclo externo, puede ser una buena elección para listas con registros grandes y claves pequeñas.

PSEUDOCÓDIGO

ALGORITMO SELECCIÓN

INICIO

ENTERO I, J, MIN, ARREGLO[N]

I ß 0

MIENTRAS(I < N)

{

MIN ß I

J ß I + 1

MIENTRAS(J < N)

{

SI(ARREGLO[J] < ARREGLO[I])

{

MIN ß J

INTERCAMBIA(ARREGLO[MIN],ARREGLO[I])

}

J ß J + 1

}

I ß I + 1

}

FIN

CÓDIGO EN C++

void seleccion(void)

{

int i, j, min, ARREGLO[N], aux;

i = 0

while(i < N)

{

min = i;

j = i + 1;

while (j < N)

{

if(ARREGLO[j] < ARREGLO[i])

{

min = j;

aux = ARREGLO[i];

ARREGLO[i] = ARREGLO[min];

ARREGLO[min] = aux;

}

j++;

}

i++;

}

}

Ejemplo:

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.

Estabilidad: Puede que haya algo de discrepancia pero esta implementación parece ser estable, puede verificar esto ordenando un conjunto de datos que tenga un par de ellos con la misma clave, el orden relativo entre ellos es conservado, pero algunos autores dicen que no es estable.

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.

Algoritmo Shake

Conocido como doble ordenamiento de burbuja; recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo coloca en su posición y al mismo tiempo también coloca el elemento menor en su posición.

PSEUDOCÓDIGO

ALGORITMO SHAKE

INICIO

ENTERO I ß 0, ARREGLO[N]

ENTERO K ß N – 1

ENTERO MIN, MAX, J, AUX

MIENTRAS(I < K)

{

MIN ß I

MAX ß I

PARA(J ß I + 1, HASTA K, J ß J + 1)

{

SI(ARREGLO[J] < ARREGLO[MIN])

{

MIN ß J

}

SI(ARREGLO[J] > ARREGLO[MAX])

{

MAX ß J

}

}

AUX ß ARREGLO[MIN]

ARREGLO[MIN] ß ARREGLO[I]

ARREGLO[I] ß AUX

SI(MAX ß I)

{

AUX ß ARREGLO[MIN]

ARREGLO[MIN] ß ARREGLO[K]

ARREGLO[K] ß AUX

}

SI NO

{

AUX ß ARREGLO[MAX]

ARREGLO[MAX] ß ARREGLO[K]

ARREGLO[K] ß AUX

}

I ß I + 1;

K ß K – 1;

}

}

CÓDIGO EN C++

void shake(void)

{

int i = 0, ARREGLO[N];

int k = N – 1;

int min, max, j, aux;

while (i < k)

{

min = i;

max = i;

for(j = i + 1; j <= k; j++)

{

if (ARREGLO[j] < ARREGLO[min])

min = j;

if (ARREGLO[j] > ARREGLO[max])

max = j;

}

aux = ARREGLO[min];

ARREGLO[min] = ARREGLO[i];

ARREGLO[i] = aux;

if (max == i)

{

aux = ARREGLO[min];

ARREGLO[min] = ARREGLO[k];

ARREGLO[k] = aux;

}

else

{

aux = ARREGLO[max];

ARREGLO[max] = ARREGLO[k];

ARREGLO[k] = aux;

}

i++;

k–;

}

}

Ejemplo:

Tiempo de ejecución:

El bucle interno se efectuará ; el bucle interior se ejecutará entonces por la regla de la multiplicación tenemos Þ O(n2)

Ventajas:

• Relativamente fácil de implementar.
• No requiere memoria adicional.

Estabilidad: Es inestable no mantiene el orden relativo de los registros.

Desventajas:

• Realiza numerosas comparaciones.
• Realiza numerosos intercambios.

Algoritmo SHELL

Ordenamiento por intervalos decrecientes, nombrado así debido a su inventor Donald Shell, este algoritmo ordena subgrupos de elementos separados K unidades respecto de su posición en el arreglo. El valor K es llamado intervalo. Después de que los primeros K subgrupos fueron ordenados generalmente utilizando Inserción Directa, se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.

Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa. El método se basa en tomar como salto al principio N/2, siendo N el número de elementos, y luego se va reduciendo a la mitad en cada repetición hasta lograr un valor de 1.

PSEUDOCÓDIGO

ALGORITMO SHELL

INICIO

ENTERO INTERVALO, K, J, I, AUX

INTERVALO ß N DIV 2

MIENTRAS(INTERVALO > 0)

{

PARA(I ß INTERVALO – 1, HASTA ß N, I ß I + 1)

{

J ß I – INTERVALO

MIENTRAS(J >= 0)

{

K ß J + INTERVALO

SI(VECTOR[K] <= VECTOR[J])

{

AUX ß VECTOR[J]

VECTOR[J] ß VECTOR[K]

VECTOR[K] ß AUX

}

SI NO

{

J ß 0

}

J ß J – INTERVALO

}

}

INTERVALO ß INTERVALO DIV 2

}

}

CÓDIGO EN C++

void shell(void)

{

int intervalo, k, j, i, aux;

intervalo = RANGO / 2;

while(intervalo > 0)

{

for(i = intervalo – 1; i < RANGO; i++)

{

j = i – intervalo;

while(j >= 0)

{

k = j + intervalo;

if(vector[k] <= vector[j])

{

aux = vector[j];

vector[j] = vector[k];

vector[k] = aux;

}

else

j = 0;

j = j – intervalo;

ver_valores(vector);

}

}

intervalo = intervalo / 2;

}

}

Ejemplo:

Tiempo de ejecución:

El bucle externo se ejecutará, el redondeo de veces, el interno n veces, luego el bucle mas interno depende de j Þ j O(n) la constante j se absorbe, luego tenemos O * o(n) Þ O(n2)

Ventajas:

• No requiere memoria adicional.
• Mejor rendimiento que el método de Inserción clásico

Estabilidad: Es inestable no mantiene el orden relativo de los registros.

Desventajas:

• Implementación algo confusa.
• Realiza numerosas comparaciones e intercambios.

Ejercicios de aplicación

1. Implemente el algoritmo de ordenación burbuja, mejore el rendimiento del algoritmo, centre su trabajo en el bucle interno.
2. Implemente el algoritmo de ordenación shake, ¿Qué mejoras le encuentra respecto al de burbuja?
3. Implemente el algoritmo de ordenación selección.
4. Implemente el algoritmo de ordenación inserción.
5. Implemente el algoritmo de ordenación shell. ¿Qué función cumplen los intervalos decrecientes de este algoritmo?

BIBLIOGRAFIA

• CEBALLOS SIERRA, FCO. JAVIER, Curso de Programación en C++. Madrid, Ed. Ra-Ma
• JOYANES AGUILAR, LUIS. Programación en C++ algoritmos, Estructuras de Datos y Objetos.

Ed. McGraw-Hill. 2000.

• JOYANES AGUILAR, Luis. Fundamentos de Programación, Algoritmos y Estructuras de datos. Seg. Edición McGraw-Hill. 1996
• BRASSARD, G.: "Fundamentos de algoritmia". Prentice Hall.

Autor:

Rolf Pinto López

Ingeniero de Sistemas