Búsqueda y ordenación externa

Algoritmos de Búsqueda

Esta operación consiste en localizar el o los registros del fichero que cumplan cierta condición. La búsqueda se suele realizar de forma que uno o varios campos del registro contengan unos valores predeterminados. Denominaremos al campo o campos por los que se realiza la búsqueda clave de búsqueda. Si la búsqueda tiene éxito, se recupera el registro que cumple el criterio de búsqueda (o todos los registros que lo cumplan); si fracasa, se debe informar al usuario o al módulo que solicitó la operación de búsqueda.
Para hacer la descripción más general, consideraremos búsquedas que se realizan por un solo campo, pudiendo adaptarse fácilmente los algoritmos propuestos para hacer búsquedas por varios campos. Consideraremos ficheros formados por registros de tipo REGISTRO, que incluyen al menos un campo, que denominaremos CLAVE, y que se toma como clave de búsqueda.
    REGISTRO es registro compuesto por
                CLAVE de tipo T
                ** otros campos de algún tipo
    fin-registro

Si las búsquedas se realizan sobre archivos ordenados por el campo tomado como clave de búsqueda, se puede forzar el final de la búsqueda cuando se llegue a un registro cuya clave contenga un valor superior al buscado, en el caso de ordenación ascendente, o inferior al buscado, en caso de ordenación descendente.
Los algoritmos de búsqueda en archivos desordenados también se pueden aplicar a archivos ordenados por la clave de búsqueda.
Tipos de búsqueda:

Algoritmos de Ordenación

Un archivo está ordenado o clasificado de forma ascendente (o descendiente) si tiene todos sus registros en secuencia ascendente (o descendiente) respecto al valor de un campo que denominamos clave de ordenación.
Si el tamaño del archivo a ordenar permite cargarlo en memoria principal, lo más adecuado es aplicarle algún algoritmo de ordenación interna y copiar los datos ordenados en el archivo original. En caso contrario, será necesario aplicar algún algoritmo de ordenación externa.
Muchos algoritmos de clasificación externa se basan en la realización de sucesivas particiones y mezclas o fusiones del archivo a clasificar. Las particiones generan dos o más archivos a partir de otro; las mezclas combinan archivos ordenados o parcialmente ordenados, obteniendo un archivo que mantiene el orden. Ambos tipos de operaciones implicarán continuos accesos a la memoria secundaria, para leer o escribir registros en los ficheros, así como varios ficheros auxiliares. Cuanto mayor sea el número de accesos a disco, más lento será el método de ordenación.
Los métodos de ordenación que comentaremos trabajan sobre ficheros que contienen registros del tipo REGISTRO, que contiene al menos un campo, denominado CLAVE, que se utilizará para ordenar el fichero de forma ascendente:

Definición de elementos

Se denomina archivo o fichero a un conjunto de informaciones estructuradas en unidades de acceso denominadas registros, todos del mismo tipo, que se almacenan en algún soporte de memoria secundaria.
Un registro es una estructura de datos formada por uno o más elementos, denominados campos, que pueden ser de diferentes tipos y que, a su vez, pueden estar compuestos por subcampos.
Los registros suelen tener un campo especial, denominado clave o identificativo, que permite identificar al registro o establecer un criterio para las operaciones. En algunos ficheros las claves son únicas, mientras que en otros pueden repetirse en diferentes registros. Pueden existir varios campos clave, en cuyo caso se habla de claves primaria, secundaria,...
En este tema trabajaremos sobre archivos con acceso secuencial. Se denomina acceso al procedimiento a seguir para posicionarse sobre un registro concreto, con la intención de realizar sobre el mismo una operación de lectura o escritura. En los ficheros secuenciales el acceso a los registros se realiza según el orden de almacenamiento de los mismos dentro del fichero, de uno en uno a partir del primero. Para acceder al registro n es necesario acceder a los n-1 anteriores.

Operaciones básicas

Las operaciones básicas para el trabajo con un archivo secuencial son: apertura, cierre, lectura, escritura y comprobación de fin de fichero. Estas operaciones se realizarán mediante funciones predefinidas del lenguaje de programación utilizado. La primera operación que se realizará es la de apertura y la última la de cierre. Una vez abierto el fichero se podrán hacer lecturas o escrituras. Cuando el objetivo sea realizar lecturas, se deberá comprobar si se ha alcanzado el final del fichero antes de intentar leer, para evitar errores.
Para trabajar con un fichero desde un programa, se asocia al nombre del archivo físico (el que reside en disco) un nombre lógico, mediante una instrucción del lenguaje considerado. En general, esta asignación se realiza en la operación de apertura. Una vez obtenido el nombre lógico del fichero, todas las operaciones sobre el fichero se realizarán utilizando dicho nombre.
Supondremos que trabajamos con ficheros que contiene registros de tipo REGISTRO:
    ** estructura de los datos del fichero
    REGISTRO es registro compuesto por
                ** campos de algún tipo
                ** . . .
    fin-registro

Trabajaremos con un fichero físico denominado NOMBRE_F, al cual se asociará el fichero lógico F. El nombre físico del fichero puede incluir el path, considerándose en cualquier caso como una cadena de caracteres:
    NOMBRE_F cadena                  ** nombre físico del fichero

    F es archivo de REGISTRO      ** nombre lógico del fichero

Se utilizar&oaacute; una variable para realizar las operaciones de lectura o escritura, que será de tipo REGISTRO y permitirá intercambiar registros entre el fichero y el programa:
    REG_BUFFER de tipo REGISTRO

La operación de apertura reserva un archivo secuencial en exclusiva para el programa que lo ejecuta. Un archivo secuencial se puede abrir o para hacer lecturas o para hacer escrituras, lo que se indicará en el momento de la apertura. Si la apertura tiene éxito, se obtendrá un nombre lógico para el fichero, con el que se trabajará en el resto del programa para hacer cualquier referencia al fichero. Si la apertura no tiene éxito, no se podrá trabajar sobre el fichero. Para simplificar los algoritmos tratados en el tema, no se incluye una comprobación sobre el éxito de la operación de apertura, considerando que siempre ha tenido éxito. Esta comprobación debe tener en cuenta el retorno obtenido en la operación de
apertura. La apertura de un fichero indica el nombre físico del fichero y el modo en el que se abre. Existen 3 modos de apertura:
lectura: si queremos leer el contenido del fichero. El puntero de lectura queda sobre el primer registro. El fichero indicado debe existir; de lo contrario se producirá un error en la apertura. 
    F ← Abrir NOMBRE_FICHERO para lectura

escritura: si deseamos escribir en el fichero, eliminando los posibles datos que contenga. El puntero de escritura se coloca al comienzo del archivo. Si el archivo no existe, se crea; si ya existe, borra su contenido, salvo que el sistema disponga de protección para que esto último no ocurra. 
    F ← Abrir NOMBRE_FICHERO para escritura

añadir: si deseamos escribir en el fichero y preservar el posible contenido del mismo, con lo que la escritura comienza a partir del final del fichero. 
    F ← Abrir NOMBRE_FICHERO para añadir

La operación de cierre libera el archivo del programa, quedando a disposición de cualquier programa que lo solicite:
    Cerrar F

Si el archivo se había abierto para escritura, la operación de cierre coloca una marca especial de fin de archivo que será detectada en posteriores lecturas.
En un fichero abierto para escritura se puede solicitar la escritura de un nuevo dato, contenido en un registro buffer. El contenido de dicho registro se colocará en el lugar identificado por el puntero de escritura y éste avanza al siguiente registro del archivo:
    Escribir F, REG_BUFFER

Para realizar una lectura sobre un fichero abierto para lectura, se indica la variable que almacenará el registro leído del fichero:
    Leer F, REG_BUFFER

Si quedan datos por leer, se coloca el contenido del registro apuntado por el puntero de lectura sobre el registro buffer, avanzando dicho puntero al siguiente registro.
Antes de realizar una lectura es necesario comprobar que no se ha llegado al final del fichero (que quedan registros por leer), para evitar un error. La operación de comprobación de final de archivo es una función booleana que toma el valor Verdadero si el puntero de lectura señala la marca especial de fin de archivo, es decir, si no quedan registros por leer, y toma el valor Falso en caso contrario:
    FF( F )


Volver al índice



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