5 Ordenar ficheros secuenciales
A veces necesitaremos ordenar el contenido de un fichero secuencial, ya sea de longitud de registro variable o constante.
Debido a la naturaleza de estos archivos, en general no será posible usar los métodos de ordenamiento que usaríamos con tablas en memoria. En muchas ocasiones trabajaremos con archivos muy grandes, de modo que será imposible ordenarlos en memoria y después reconstruirlos en disco.
Algoritmo de mezcla natural
En cuanto a los ficheros secuenciales, el método más usado es el de mezcla natural. Es válido para ficheros de tamaño de registro variable.
Es un buen método para ordenar barajas de naipes, por ejemplo.
Cada pasada se compone de dos fases. En la primera se separa el fichero original en dos auxiliares, los elementos se dirigen a uno u otro fichero separando los tramos de registros que ya estén ordenados. En la segunda fase los dos ficheros auxiliares se mezclan de nuevo de modo que de cada dos tramos se obtiene siempre uno ordenado. El proceso se repite hasta que sólo obtenemos un tramo.
Por ejemplo, supongamos los siguientes valores en un fichero de acceso secuencial, que ordenaremos de menor a mayor:
3, 1, 2, 4, 6, 9, 5, 8, 10, 7
Separaremos todos los tramos ordenados de este fichero:
[3], [1, 2, 4, 6, 9], [5, 8, 10], [7]
La primera pasada separará los tramos alternándolos en dos ficheros auxiliares:
aux1: [3], [5, 8, 10]
aux2: [1, 2, 4, 6, 9], [7]
Ahora sigue una pasada de mezcla, mezclaremos un tramo de cada fichero auxiliar en un único tramo:
mezcla: [1, 2, 3, 4, 6, 9], [5, 7, 8, 10]
Ahora repetimos el proceso, separando los tramos en los ficheros auxiliares:
aux1: [1, 2, 3, 4, 6, 9]
aux2: [5, 7, 8, 10]
Y de mezclándolos de nuevo:
mezcla: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
El fichero ya está ordenado, para verificarlo contaremos los tramos obtenidos después de cada proceso de mezcla, el fichero estará desordenado si nos encontramos más de un tramo.
Ejemplo
// mezcla.c : Ordenamiento de archivos secuenciales
// Ordena ficheros de texto por orden alfabético de líneas
// Usando el algoritmo de mezcla natural
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void Mostrar(FILE *fich);
void Mezcla(FILE *fich);
void Separar(FILE *fich, FILE **aux);
int Mezclar(FILE *fich, FILE **aux);
int main()
{
FILE *fichero;
fichero = fopen("mezcla.txt", "r+");
puts("Fichero desordenado\n");
Mostrar(fichero);
puts("Ordenando fichero\n");
Mezcla(fichero);
puts("Fichero ordenado\n");
Mostrar(fichero);
fclose(fichero);
system("PAUSE");
return 0;
}
// Muestra el contenido del fichero "fich"
void Mostrar(FILE *fich)
{
char linea[128];
rewind(fich);
fgets(linea, 128, fich);
while(!feof(fich)) {
puts(linea);
fgets(linea, 128, fich);
}
}
// Algoritmo de mezcla:
void Mezcla(FILE *fich)
{
int ordenado;
FILE *aux[2];
// Bucle que se repite hasta que el fichero esté ordenado:
do {
// Crea los dos ficheros auxiliares para separar los tramos:
aux[0] = fopen("aux1.txt", "w+");
aux[1] = fopen("aux2.txt", "w+");
rewind(fich);
Separar(fich, aux);
rewind(aux[0]);
rewind(aux[1]);
rewind(fich);
ordenado = Mezclar(fich, aux);
fclose(aux[0]);
fclose(aux[1]);
} while(!ordenado);
// Elimina los ficheros auxiliares:
remove("aux1.txt");
remove("aux2.txt");
}
// Separa los tramos ordenados alternando entre los ficheros auxiliares:
void Separar(FILE *fich, FILE **aux)
{
char linea[128], anterior[2][128];
int salida = 0;
// Volores iniciales para los últimos valores
// almacenados en los ficheros auxiliares
strcpy(anterior[0], "");
strcpy(anterior[1], "");
// Captura la primero línea:
fgets(linea, 128, fich);
while(!feof(fich)) {
// Decide a qué fichero de salida corresponde la línea leída:
if(salida == 0 && strcmp(linea, anterior[0]) < 0) salida = 1;
else if(salida == 1 && strcmp(linea, anterior[1]) < 0) salida = 0;
// Almacena la línea actual como la última añadida:
strcpy(anterior[salida], linea);
// Añade la línea al fichero auxiliar:
fputs(linea, aux[salida]);
// Lee la siguiente línea:
fgets(linea, 128, fich);
}
}
// Mezcla los ficheros auxiliares:
int Mezclar(FILE *fich, FILE **aux)
{
char ultima[128], linea[2][128], anterior[2][128];
int entrada;
int tramos = 0;
// Lee la primera línea de cada fichero auxiliar:
fgets(linea[0], 128, aux[0]);
fgets(linea[1], 128, aux[1]);
// Valores iniciales;
strcpy(ultima, "");
strcpy(anterior[0], "");
strcpy(anterior[1], "");
// Bucle, mientras no se acabe ninguno de los ficheros auxiliares (quedan tramos por mezclar):
while(!feof(aux[0]) && !feof(aux[1])) {
// Selecciona la línea que se añadirá:
if(strcmp(linea[0], linea[1]) <= 0) entrada = 0; else entrada = 1;
// Almacena el valor como el último añadido:
strcpy(anterior[entrada], linea[entrada]);
// Añade la línea al fichero:
fputs(linea[entrada], fich);
// Lee la siguiente línea del fichero auxiliar:
fgets(linea[entrada], 128, aux[entrada]);
// Verificar fin de tramo, si es así copiar el resto del otro tramo:
if(strcmp(anterior[entrada], linea[entrada]) > 0) {
if(!entrada) entrada = 1; else entrada = 0;
tramos++;
// Copia lo que queda del tramo actual al fichero de salida:
do {
strcpy(anterior[entrada], linea[entrada]);
fputs(linea[entrada], fich);
fgets(linea[entrada], 128, aux[entrada]);
} while(!feof(aux[entrada]) && strcmp(anterior[entrada], linea[entrada]) <= 0);
}
}
// Añadir tramos que queden sin mezclar:
if(!feof(aux[0])) tramos++;
while(!feof(aux[0])) {
fputs(linea[0], fich);
fgets(linea[0], 128, aux[0]);
}
if(!feof(aux[1])) tramos++;
while(!feof(aux[1])) {
fputs(linea[1], fich);
fgets(linea[1], 128, aux[1]);
}
return(tramos == 1);
}
Ordenar archivos es siempre una tarea muy lenta y requiere mucho tiempo. Este algoritmo, además requiere el doble de espacio en disco del que ocupa el fichero a ordenar, por ejemplo, para ordenar un fichero de 500 megas se necesitan otros 500 megas de disco libres.
Sin embargo, un fichero como el mencionado, sería muy difícil de ordenar en memoria.