Algoritmo de ordenación de raíz

Esta técnica de ordenación se puede utilizar para tratar ficheros con claves numéricas enteras. La ordenación se realiza aplicando sucesivas iteraciones, en las que primero se realiza una partición y a continuación una concatenación. En la primera etapa se distribuyen los registros en archivos auxiliares en función de la cifra de la clave que corresponda con la iteración que se está realizando. En la segunda etapa se concatenan los 10 archivos sobre el archivo original. Los dígitos de la clave se toman de derecha a izquierda (empezando por las unidades), completándose la ordenación en tantas iteraciones como dígitos tenga la clave que incluya más cifras.
PSEUDOCÓDIGO
    MÓDULO Ordenacion_de_raiz
    DATOS
       PARÁMETROS
             Recibe NOMBRE_F cadena               ** fichero original
             Recibe NOMBRE_F_AUX(10) de cadenas   ** ficheros auxiliares
       VARIABLES
             SEGUIR lógica         ** seguir/no seguir con las iteraciones
             ITERACION entera      ** contador de iteraciones
    INICIO
          SEGUIR ← Verdadero   ** seguir iterando
          ITERACION ← 1
           Repetir
               Separar (NOMBRE_F, NOMBRE_F_AUX, ITERACION, SEGUIR)
               Concatenar (NOMBRE_F, NOMBRE_F_AUX)
              ITERACION ← ITERACION +1
           Hasta que (SEGUIR = Falso)
    FIN

CÓDIGO C

PRONTO SERÁ INCORPORADO....

El módulo Separar realiza una partición de un fichero origen en 10 ficheros destino. La partición se realiza copiando cada registro del fichero origen en el destino que le corresponda, en función de la cifra de la clave coincidente con la posición dada por ITERACION: si la cifra es 0, el registro se lleva al primer fichero destino, si es 1, se lleva al segundo,..., si es 8 se lleva al penúltimo y si es 9 se lleva al último. El parámetro SEGUIR tomará valor Falso si no deben proseguir las iteraciones (si se han procesado todas las cifras de la clave más larga).
PSEUDOCÓDIGO
    MÓDULO Separar
    DATOS
       PARÁMETROS
             Recibe NOMBRE_ORIGEN cadena              ** fichero a ordenar
             Recibe NOMBRE_DESTINO(10) de cadenas     ** ficheros auxiliares
             Recibe ITERACION entera                  ** iteración actual
             Transforma SEGUIR lógica                 ** seguir/no seguir ordenando
       VARIABLES
             REG de tipo REGISTRO                     ** registro de un fichero
             CIFRA entero                             ** una cifra de la clave
             F_O fichero de REGISTRO                  ** fichero origen
             F_D(10) de ficheros de REGISTRO          ** ficheros destino
             I entera                                 ** contador
    INICIO
          SEGUIR ← Falso
           Para I desde 1 hasta 10
              F_D(I) ← Abrir NOMBRE_DESTINO(I) para escritura
           fin-para
          F_O ← Abrir NOMBRE_ORIGEN para lectura
           Mientras ( FF(F_O) = Falso) hacer
              Leer REG, F_O
               CIFRA ← Obtener_cifra(REG.CLAVE, ITERACION, SEGUIR)
              Escribir REG, F_D(CIFRA+1)
           fin-mientras
           Para I desde 1 hasta 10
              Cerrar F_D(I)
           fin-para
          Cerrar F_O
    FIN

CÓDIGO C

PRONTO SERÁ INCORPORADO....

El módulo Obtener_cifra obtiene la cifra de la clave que corresponde a la iteración actual del algoritmo. Además, indica si el algoritmo de ordenación debe continuar con las iteraciones (si la clave tiene al menos otra cifra a la izquierda de la considerada):
PSEUDOCÓDIGO
    MÓDULO Obtener_cifra devuelve entero
    DATOS
       PARÁMETROS
             Recibe CLAVE entero            ** clave de un registro
             Recibe ITERACION entero        ** iteración actual
             Transforma SEGUIR lógica       ** seguir/no seguir iterando
       VARIABLES
             I entero                  ** contador
             CIFRA entero              ** una cifra de la clave
             N entero                  ** copia de la clave
    INICIO
          N ← CLAVE
           Para I desde 1 hasta ITERACION
              CIFRA ← N MOD 10         ** resto de la división
              N ← N DIV 10             ** división entera
           fin-para
           Si (N ≠ 0) entonces
              SEGUIR ← Verdadero
           fin-si
          DEVOLVER CIFRA
    FIN

CÓDIGO C

PRONTO SERÁ INCORPORADO....

El módulo Concatenar copia el contenido de los 10 ficheros auxiliares sobre el fichero original, empezando por el fichero 1 y terminando por el 10:
PSEUDOCÓDIGO
    MÓDULO Concatenar
    DATOS
       PARÁMETROS
             Recibe NOMBRE_DESTINO cadena           ** fichero a ordenar
             Recibe NOMBRE_ORIGEN(10) de cadenas    ** ficheros auxiliares
       VARIABLES
             REG de tipo REGISTRO  
             F_D fichero de REGISTRO
             F_O(10) de ficheros de REGISTRO
             I entera   
    INICIO
           Para I desde 1 hasta 10
              F_O(I) ← Abrir NOMBRE_ORIGEN(I) para lectura
           fin-para
          F_D ← Abrir NOMBRE_DESTINO para escritura
           Para I desde 1 hasta 10
               Mientras ( FF(F_O(I)) = Falso ) hacer
                  Leer REG, F_O(I)
                  Escribir REG, F_D
               fin-mientras
           fin-para
           Para I desde 1 hasta 10
              Cerrar F_O (I)
           fin-para
          Cerrar F_D
    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 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 ...
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