|
|
|
|
Algoritmo de Ordenamiento
Tenemos un grupo de registros a ordenar.
Creamos un arreglo para dirigir el ordenamiento que se llaman cabeceras, cada cabecera corresponde a la dirección del primer registro de un grupo ordenado de registros, por ejemplo se tiene la serie a ordenar de menor a mayor con los siguientes datos: a[10]= {2, 50, 25, 30, 35, 100, 85, 65, 27, 30}.
Las cabeceras serían C(1)=1, C(2)=3, C(3)=7, C(4)=8, C(5)=9. Correspondientes a los valores de registros 2, 25, 85, 65, 27
La cantidad de arrays (arreglos) necesarios son: el arreglo original "a", el arreglo que contenga las cabeceras "C" y el arreglo temporal para el merge "T", y algunos índices para poder poder ejecutar el sort.
Ahora a ordenar de menor a mayor.
IDEA INICIAL-01
PRIMERA PARTE
i = 1 ; contador de registros del arreglo “a”
imax = xxx ; cantidad de registros a ordenar de “a”
j = 0 ; contador para el arreglo de cabeceras “C”
Do while i < imax
If a(i) > a(i + 1)
c(j++) = a(i) ;
endif
enddo
jmax = j ; último índice “j” usado.
El código anterior corresponde a la primera pasada (lectura de los datos) comparando el primero con el segundo y si el primero es menor que el segundo, mantengo el primer dato como cabecera de lista,
luego comparo el segundo con el tercero, aquí hay dos casos:
a) si el segundo es menor o igual que el tercero, entonces mantengo la cabecera y continúo con el paso 1.
b) si el segundo es mayor que el tercero, entonces creo una nueva cabecera de lista y continúo con el paso 1.
Paso 1. comparo el tercero con el cuarto y ejecuto lo mismo como si fuera el segundo con el tercero y así sucesivamente hasta completar todos los elementos.
SEGUNDA PARTE
La segunda parte de este sort que también lo vislumbró el Ing. Rafael Estartús, después de comentarle la primera parte, fue que al obtener estas sub-listas me quedan como un quipu (la manera de contar de los incas peruanos) de datos, entonces lo que sigue es un merge (otro tipo de sort muy usado) de cada sub-lista. Y de esta manera tienes todos los datos ordenados, si quieres ver el algoritmo del merge lo puedes ver en http://mailweb.udlap.mx/~sainzmar/is211/algoritMerge.html pero esto lo puedes simplificar ya no sub-dividiendo si no uniendo dos sub-listas cada vez hasta terminar.
k = 1 ; contador auxiliar
Do while
k < jmax
n = 1 ; índice de arreglo “T”
For m = 1 to C(k + 1) – 1
T(n++)
= a(m)
Next m
If k + 1 = jmax
ult = imax ;
else
ult = C(k + 2) ;
endif
Do submerge (
1, C(k + 1), ult )
enddo
quit
proc submerge
; subrutina merge
parameters ini1, ini2, ultimo
i1 = ini1
i2 = ini2
do while ( ( i1 < ini2 ) .or. ( i2 < ultimo ) )
if
T(i1) <= a(i2)
a(ini1++)
= T(i1++);
else
a(ini1++)
= a(i2++);
endif
enddo
if i1 < ini2 – 1
for i2
= i1 to ini2 – 1
a(ini1++)
= T(i1++) ;
next
i2
endif
Esto como idea original era bastante buena para mí. Pero después de darle algunas vueltas y haciendo cálculos mentales de cantidad de comparaciones, llegué a la segunda idea.
IDEA 02
El merge consume muchos recursos innecesarios, así que llegué a la conclusión que en vez de juntar la primer sub-lista con la segunda sub-lista, y lo que obtenía volver a juntarlo (merge) con la tercera sub-lista, para que de este resultado juntarlo con la cuarta sub-lista, era un consumo de muchos pasos, así que decidí hacer la siguiente mejora:
Juntar la sub-lista-1 con la sub-lista-2, la sublista-3 con la sublista-4, la sub-lista-5 con la sub-lista-6 y así sucesivamente, de esta manera el número de procesos en comparaciones e inserciones para juntarlos se reducía. Luego se procedía las nuevas cabeceras de sub-listas con el mismo cirterio hasta terminar y tener los datos ordenados.
Dejo al lector la aplicación de esta
mejora y la siguiente en el programa inicial mostrado.
IDEA 03
Esta tercera mejora continuaba con la idea 02, en el sentido que en vez de la primera pasada de 1 con 2 y luego 2 con 3 para ir obteniendo cabeceras y sub-listas, esto consumía recursos, para lo cual me podía bastar comparar 1 con 2 y luego 3 con 4, obteniendo 2 sub-listas con sus cabeceras, reduciendo el número de comparaciones, para luego continuar con el paso siguiente del merge optimizado.
Atentamente,
G.
Telef. + 51 – 73 – 304575 (Perú)
E-mail : javidil@hotmail.com
bravenet.com