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