Algoritmo de ordenación por mezcla natural
En cada iteración, en primer lugar se separan los registros del fichero origen en otros dos ficheros, copiando en cada uno las secuencias de registros consecutivos que ya están ordenados entre sí en el origen. A continuación, se mezclan los dos ficheros auxiliares, obteniendo de cada dos tramos ordenados otro ordenado. El proceso de ordenación se repite hasta que se obtiene un solo tramo.
PSEUDOCÓDIGO
MÓDULO Clasificacion_mezcla_natural
DATOS
PARÁMETROS
Recibe NOMBRE_F cadena ** fichero a ordenar
Recibe NOMBRE_F1 cadena ** primer fichero auxiliar
Recibe NOMBRE_F2 cadena ** segundo fichero auxiliar
VARIABLES
L entera ** num. de subsecuencias ordenadas mezcladas
INICIO
Repetir
Separar (NOMBRE_F, NOMBRE_F1, NOMBRE_F2)
Mezcla_natural (NOMBRE_F, NOMBRE_F1, NOMBRE_F2, L)
Hasta que (L = 1)
FIN
CÓDIGO C
PRONTO SERÁ INCORPORADO....
El módulo Separar copia en el primer fichero auxiliar la primera secuencia ordenada que encuentre en el fichero origen; a continuación, copia la segunda secuencia ordenada en el segundo fichero auxiliar. El proceso continúa, copiando alternativamente en cada uno de los dos ficheros auxiliares, hasta que se hayan procesado todos los registros del fichero a ordenar:
PSEUDOCÓDIGO
MÓDULO Separar
DATOS
PARÁMETROS
Recibe NOMBRE_F cadena ** fichero que se va a partir
Recibe NOMBRE_F1 cadena ** primer fichero auxiliar
Recibe NOMBRE_F2 cadena ** segundo fichero auxiliar
VARIABLES
REG de tipo REGISTRO
F, F1, F2 archivos de REGISTRO
INICIO
F1 ← Abrir NOMBRE_F1 para escritura
F2 ← Abrir NOMBRE_F2 para escritura
F ← Abrir NOMBRE_F para lectura
Leer F, REG
Repetir
Copiar_secuencia (F, F1, REG)
Si ( FF(F) = Falso) entonces
Copiar_secuencia (F, F2, REG)
fin-si
Hasta que (FF(F) = Verdadero)
Cerrar F
Cerrar F1
Cerrar F2
FIN
CÓDIGO C
PRONTO SERÁ INCORPORADO....
El módulo Copiar_secuencia copia en un fichero destino la siguiente secuencia ordenada que se encuentre en el origen. El proceso concluye cuando se encuentra el primer valor que no está ordenado respecto al último copiado en el fichero destino (es decir, cuando el valor leído del fichero origen sea menor que el último escrito en el destino), o cuando ya no queden registros por procesar en el fichero origen, lo que primero ocurra.
PSEUDOCÓDIGO
MÓDULO Copiar_secuencia
DATOS
PARÁMETROS
Recibe F_O archivo de REGISTRO ** fichero origen
Transforma F_D archivo de REGISTRO ** fichero destino
Transforma REG de tipo REGISTRO ** reg. leído del fichero origen
VARIABLES
PARAR lógica
INICIO
PARAR ← Falso
Repetir
Escribir F_D, REG
Leer_y_chequear (F_O, REG, PARAR)
Hasta (PARAR = Verdadero)
FIN
CÓDIGO C
PRONTO SERÁ INCORPORADO....
El módulo Leer_y_chequear comprueba si se ha llegado al final del fichero indicado, o si se ha llegado al final de la secuencia ordenada. En cualquiera de los dos casos, pone a Verdadero el último parámetro pasado en la llamada:
PSEUDOCÓDIGO
MÓDULO Leer_y_chequear
DATOS
PARÁMETROS
Recibe FICH archivo de REGISTRO ** fichero abierto para lectura
Transforma REG de tipo REGISTRO ** reg. leído del fichero origen
Transforma PARAR lógica
VARIABLES
REG_SIG de tipo REGISTRO
INICIO
Si (FF(FICH) = Falso) entonces
Leer FICH, REG_SIG
Si (REG.CLAVE > REG_SIG.CLAVE) entonces
PARAR ← Verdadero
fin-si
REG ← REG_SIG
sino
PARAR ← Verdadero
fin-si
FIN
CÓDIGO C
PRONTO SERÁ INCORPORADO....
El módulo Mezcla_natural obtiene un nuevo fichero mezclando el contenido de los dos ficheros auxiliares. La mezcla se realiza sobre cada par de secuencias ordenadas existentes en los ficheros auxiliares, que pueden ser de longitudes diferentes. Si sólo se ha mezclado una secuencia procedente de cada origen, el fichero obtenido ya estará ordenado:
PSEUDOCÓDIGO
MÓDULO Mezcla_natural
DATOS
PARÁMETROS
Recibe NOMBRE_F cadena ** fichero resultado
Recibe NOMBRE_F1 cadena ** primer fichero auxiliar
Recibe NOMBRE_F2 cadena ** segundo fichero auxiliar
Transforma L entera ** num. de secuenc. mezcladas
VARIABLES
R1, R2 de tipo REGISTRO
FIN_ORDEN booleana
F, F1, F2 archivo de REGISTRO
INICIO
F1 ← Abrir NOMBRE_F1 para lectura
F2 ← Abrir NOMBRE_F2 para lectura
F ← Abrir NOMBRE_F para escritura
L ← 0
Leer F1, R1
Leer F2, R2
Repetir
FIN_ORDEN ← Falso
Mientras (FIN_ORDEN = Falso) hacer
Si (R1.CLAVE < R2.CLAVE) entonces
Escribir F, R1
Leer_y_chequear(F1, R1, FIN_ORDEN)
Si (FIN_ORDEN = Verdadero) entonces
Copiar_secuencia(F2, F, R2)
fin-si
sino
Escribir F, R2
Leer_y_chequear (F2, R2, FIN_ORDEN)
Si (FIN_ORDEN = Verdadero) entonces
Copiar_secuencia(F1, F, R1)
fin-si
fin-si
fin-mientras
L ← L + 1
Hasta que ( (FF(F1) = Verdadero) O (FF(F2) = Verdadero))
** copias de colas
Mientras (FF(F1) = Falso) hacer
Copiar_secuencia(F1, F, R1)
L ← L+1
fin-mientras
Mientras (FF(F2) = Falso) hacer
Copiar_secuencia(F2, F, R2)
L ← L+1
fin-mientras
FIN
CÓDIGO C
PRONTO SERÁ INCORPORADO....
Comentarios
Publicar un comentario