Algoritmo de ordenación por mezcla directa

La ordenación por mezcla directa realiza sucesivas operaciones de partición y mezcla, que producen secuencias ordenadas de longitud cada vez mayor. La primera partición se hace en secuencias de longitud 1, y la fusión correspondiente produce sobre el archivo inicial secuencias ordenadas de longitud 2. En cada nueva partición y fusión se duplica la longitud de las secuencias ordenadas obtenidas. El proceso termina cuando la longitud de la secuencia ordenada es mayor o igual que la longitud del archivo a ordenar.
PSEUDOCÓDIGO
    MÓDULO Ordenacion_mezcla_directa
    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
           NUM_ELEM entero            ** num. de registros a ordenar
           TAM_SEC entero                ** tamaño de la secuencia actual
    INICIO
           TAM_SEC ← 1
            Repetir
                Separar (NOMBRE_F, NOMBRE_F1, NOMBRE_F2, TAM_SEC, NUM_ELEM)
                Mezcla_directa (NOMBRE_F, NOMBRE_F1, NOMBRE_F2,TAM_SEC, NUM_ELEM)
               TAM_SEC ← 2 * TAM_SEC
            Hasta que (TAM_SEC  ≥ NUM_ELEM)
    FIN

CÓDIGO C

PRONTO SERÁ INCORPORADO....

El siguiente módulo realiza la partición, copiando de forma alternativa en cada fichero auxiliar una secuencia de TAM_SEC registros consecutivos procedentes del fichero a ordenar. La última secuencia copiada puede tener menos de TAM_SEC registros:
PSEUDOCÓDIGO
    MÓDULO Separar
    DATOS
       PARÁMETROS
           Recibe NOMBRE_F cadena      ** fichero a ordenar
           Recibe NOMBRE_F1 cadena     ** primer fichero auxiliar
           Recibe NOMBRE_F2 cadena     ** segundo fichero auxiliar
           Recibe TAM_SEC entero       ** tamaño de la secuencia
           Transforma ELEM_F entero    ** registros del fichero origen
       VARIABLES
            REG de tipo REGISTRO
            F, F1, F2 archivos de REGISTRO
            N entera       ** número de reg. escritos en un destino
    INICIO
           F1 ← Abrir NOMBRE_F1 para Escritura
           F2 ← Abrir NOMBRE_F2 para Escritura
           F ← Abrir NOMBRE_F para Lectura
           ELEM_F ← 0
           Leer F, REG
           ELEM_F ← ELEM _F + 1
            Mientras (FF(F) = Falso) hacer
               N ← 0
                Mientras ( (FF(F) = Falso)   Y   (N < TAM_SEC) ) hacer
                   Escribir F1, REG
                   N ← N + 1
                   Leer F, REG
                   ELEM_F ← ELEM _F + 1
                fin-mientras
               N ← 0
                Mientras ( (FF(F) = Falso)   Y   (N < TAM_SEC) ) hacer
                   Escribir F2, REG
                   N ← N + 1
                   Leer F, REG
                   ELEM_F ← ELEM_F + 1
                fin-mientras
           fin-mientras
          Cerrar F
          Cerrar F1
          Cerrar F2
    FIN

CÓDIGO C

PRONTO SERÁ INCORPORADO....

El siguiente módulo realiza la mezcla de los dos ficheros auxiliares, copiando los registros sobre el fichero a ordenar. Dicho fichero se construye mezclando secuencias ordenadas de tamaño TAM_SEC de los dos ficheros auxiliares. El parámetro ELEM_F indica el número de registros que contenía el fichero a ordenar antes de partirlo en dos. Por tanto, el fichero resultante de la mezcla debe tener tambiŕn ELEM_F registros. Cuando ya no queden registros por mezclar procedentes de uno de los dos ficheros auxiliares, se copiarán en el destino todos los registros restantes del otro fichero auxiliar (copia de cabos).
PSEUDOCÓDIGO
    MÓDULO Mezcla_directa
    DATOS
       PARÁMETROS
            Recibe NOMBRE_F cadena       ** fichero a ordenar
            Recibe NOMBRE_F1 cadena      ** primer fichero auxiliar
            Recibe NOMBRE_F2 cadena      ** segundo fichero auxiliar
            Recibe TAM_SEC entera        ** tamaño de la secuencia
            Recibe ELEM_F entera         ** registros del fichero a ordena
       VARIABLES
           REG1, REG2 de tipo REGISTRO
           RESTA_F1 entero       ** reg. de la sec. del fich. 1 por mezclar
           RESTA_F2 entero       ** reg. de la sec. del fich. 2 por mezclar
           RESTA enteros         ** reg. totales por mezclar
                   F, F1, F2 archivos de REGISTRO
    INICIO
           F1 ← Abrir NOMBRE_F1 para Lectura
           F2 ← Abrir NOMBRE_F2 para Lectura
           F ← Abrir NOMBRE_F para Escritura
           RESTA ← ELEM_F     ** registros totales que faltan por mezclar
            Repetir
                ** número de registros a mezclar del primer origen
                Si (RESTA ≥ TAM_SEC) entonces
                    RESTA_F1 ← TAM_SEC
                sino
                    RESTA_F1 ← RESTA
                fin-si
               RESTA ← RESTA - RESTA_F1
               ** número de registros a mezclar del segundo origen
                Si (RESTA ≥ TAM_SECUENCIA) entonces
                   RESTA_F2 ← TAM_SEC
                sino
                   RESTA_F2 ← RESTA
                fin-si
               RESTA ← RESTA - RESTA_F2
               Leer F1, REG1
               Leer F2, REG2
                Mientras ( (RESTA_F1 ≠ 0) Y (RESTA_F2 ≠ 0) ) hacer
                   Si (REG 1.CLAVE < REG2.CLAVE) entonces
                      Escribir F, REG1
                      RESTA_F1 ← RESTA_F1 - 1
                       Si (RESTA_F1 ≠ 0) entonces
                          Leer F1, REG1
                       fin-si
                   sino
                      Escribir F, REG2
                      RESTA_F2 ← RESTA_F2 - 1
                       Si (RESTA_F2 ≠ 0) entonces
                          Leer F2, REG2
                       fin-si
                   fin-si
                fin-mientras

               ** copia de cabos
                Mientras (RESTA_F2 ≠ 0) hacer
                   Escribir F, REG2
                   RESTA_F2 ← RESTA_F2 - 1
                    Si (RESTA_F2 ≠ 0) entonces
                       Leer F2, REG2
                    fin-si
                fin-mientras
                Mientras (RESTA_F1 ≠ 0) hacer
                   Escribir F, REG1
                   RESTA_F1 ← RESTA_F1 - 1
                    Si (RESTA_F1 ≠ 0) entonces
                       Leer F1, REG1
                    fin-si
               fin-mientras
            Hasta que (RESTA = 0)
           Cerrar F
           Cerrar F1
           Cerrar F2
    FIN

CÓDIGO C

PRONTO SERÁ INCORPORADO....

Volver al índice

Volver a Búsqueda y Ordenación Externa



Comentarios

Publicar un comentario

Entradas populares de este blog

Algoritmo de ordenación por mezcla natural

El método de ordenación por mezcla natural, al igual que el de clasificación por mezcla directa, realiza sucesivas particiones y mezclas, pero intenta aprovechar el orden existente en los datos, considerando secuencias de longitud variable. 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 mez...
Leer más

Algoritmo de Ordenación por Intercambio Directo (Burbuja)

Este método también se conoce como método de la burbuja. Tiene dos versiones basadas en la misma idea: recorrer sucesivamente el vector comparando los elementos consecutivos e intercambiándolos cuando estén descolocados. En una de las versiones el vector se recorre de izquierda a derecha, desplazando los valores mayores hacia su derecha, y en la otra se recorre de derecha a izquierda, desplazando los valores menores hacia su izquierda, ambos para la clasificación en orden ascendente. Cada pasada sobre el vector lleva un nuevo elemento a su posición definitiva, y en orden, en el extremo de la zona de comparación considerada (extremo derecho en el caso de recorrido de izquierda a derecha y en el extremo izquierdo en el caso de recorrido de derecha a izquierda), por lo que en la siguiente pasada se excluye de las comparaciones. El algoritmo consiste en aplicar los siguientes pasos, considerando inicialmente todas las posiciones del vector: Se comparan los valores de las posicione...
Leer más