Por intercalación de archivos se entienden la unión o fusión de dos o más archivos, ordenados de acuerdo con un determinado campo clave, en un solo archivo.
ORDENACIÓN DE ARCHIVOS
La ordenación de archivos se lleva a cabo cuando el volumen de los datos a tratar es demasiado grande y los mismos no caben en la memoria principal de la computadora.Al ocurrir esta situación no pueden aplicarse los métodos de ordenación interna, de modo que debe pensarse en otro tipo de algoritmos para ordenar datos almacenados en archivos.Por ordenación de archivos se entiende, entonces, la ordenación o clasificación de éstos, ascendente o descendentemente, de acuerdo con un campo determinado al que se denominará campo clave. La principal desventaja de esta ordenación es el tiempo de ejecución, debido a las sucesivas operaciones de entrada y salida.Los dos métodos de ordenación externa más importantes son los basados en la mezcla directa y en la mezcla equilibrada.
ORDENACIÓN POR MEZCLA DIRECTA
El método de ordenación por mezcla directa es probablemente el más utilizado por su fácil comprensión.La idea central de este algoritmo consiste en la realización sucesiva de una partición y una fusión que produce secuencias ordenadas de longitud cada vez mayor. En la primera pasada la participación es de longitud 1 y la fusión o mezcla produce secuencias ordenadas de longitud 4. Este proceso se repite hasta que la longitud de la secuencia para la partición sea mayor o igual que la longitud de la secuencia para la partición sea mayor o igual que el número de elementos del archivo original.
ORDENACION POR MEZCLA EQUILIBRADA
El método de ordenación por mezcla equilibrada, conocido también con el nombre de mezcla natural, es una optimización del método de mezcla directa.La idea central de este método consiste en realizar las particiones tomando secuencias ordenadas de máxima longitud en lugar de secuencias de tamaño fijo previamente determinadas. Luego realiza la fusión de las secuencias ordenadas, alternativamente sobre dos archivos aplicando estas acciones en forma repetida se lograra que el archivo original quede ordenado. Para la realización de este proceso de ordenación se necesitaran cuatro archivos. El archivo original F y tres archivos auxiliares a los que se denominaran F1, F2 y F3. De estos archivos, dos serán considerados de entrada y dos de salida; esto, alternativamente, con el objeto de realizar la fusión-partición. El proceso termina cuando en la realización de una fusión-partición el segundo archivo quede vacío.
INTERCALACIÓN SIMPLE
El método de ordenación por intercalación es utilizado por los jugadores de cartas o naipes para ordenar sus barajas. Consiste en mirar las cartas una a una y cuando se ve cada nueva carta se inserta en el lugar adecuado. Para desarrollar el algoritmo imaginemos que las cartas se encuentran situadas en una fila encima del tapete; a medida que se ve una carta nueva, ésta se compara con la fila y se debe empujar alguna de ellas a la derecha para dejar espacio e insertar la nueva.Consideremos un vector de n posiciones. Comencemos con el subíndice i en la segunda posición incrementando en 1, el elemento del subíndice del vector se elimina de la secuencia y se reinserta en el vector en la posición adecuada.
INTERCALACIÓN BINARIA
El algoritmo de ordenación por intercalación simple requiere una exploración o búsqueda secuencial para localizar la posición de un elemento en la sublista ordenada. Si en lugar de considerar una búsqueda secuencial se realizara una búsqueda binaria se mejoraría considerablemente el algoritmo y se aumentaría la velocidad de ejecución. Esta modificación se conoce como método de intercalación binaria.Este algoritmo utiliza la técnica de dividir y conquistar por lo tanto, divide el vector y toma un elemento pivote y compara contra él los elementos del vector dividido.
INTERCALACIÓN MERGE
Cuando se dispone de dos vectores ya ordenados y se desea obtener un tercer vector también ordenado, se puede realizar la ordenación con un método denominado Mezcla (Merge en ingles). Supongamos que A es un vector ordenado de m elementos y B es otro vector ordenado de n elemetos. La operación de mezcla producirá un nuevo vector de m + n elementos.El método más sencillo, pero menos eficaz, consiste en colocar una lista detrás de la otra y luego ordenarla. Sin embargo este método no aprovecha la propiedad de que los vectores A y B ya están ordenados, por ello debe recurrir normalmente al sistema de mezcla el cual cosiste en comparar los dos primeros elementos de los vectores (A y B) y enviar al menor al tercer vector, continuando con el elemento comparado pero no enviado con el siguiente elemento del vector que contiene al elemento menor comparado anteriormente y así sucesivamente. Una vez que se terminaron los elementos de un vector, se procede a vaciar los elementos restantes del otro vector.
No hay comentarios:
Publicar un comentario