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.

Comentarios de los usuarios (3)

luis
2010-03-15 15:41:38

hola, que tal?

sabes, uso constantemente los ejemplos que encuentro por aqui, y me ayudan mucho. pero tengo un problema con el codigo citado en \"ordenar ficheros/archivos secuenciales\", es el sgte:

// 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);

}

bueno, dicho codigo no me funciona.

creo el fichero mezcla.txt y este muestra su contenido, y al ordenarlo, muestra exactamente la misma lista(tanto numeros, como cadenas de caracteres). \'no hace nada\'

he tratado de corregir el codigo sin resultados. espero que puedas arreglar dicho codigo, pues lo necesito con urgencia.

un saludo

Diego
2012-03-14 04:51:11

Tranquilos compañeros, el código funciona a la perfección, quisiera darles las gracias por los conocimientos y ejemplos que ofrecen, jamás he copiado ningún ejemplo para hacer una tarea o algo, nunca, pues no me gusta, prefiero hacer yo mismo las cosas para entender y aprender, de hecho tengo mis propias bibliotecas. Lo que si hago es ver los ejemplos para sacar una idea y obviamente comprender mejor, pues ahí uno analiza ciertos detalles que pueden depender del lenguaje de programación o el usuario u otras cosas, en fin simplemente GRACIAS.

Jorge
2012-07-13 17:31:21

El código funciona para ordenar alfabéticamente las palabras de un fichero, siempre que después de la última palabra (en el fichero desordenado) pulsemos ENTER para crear una nueva línea; de lo contrario, dejará nuestra última palabra sin ordenar.

Por otro lado, la función Mostrar puede ser útil para probar este código con o sin algunas modificaciones, pero resulta demasiado pesada cuando se trata de ordenar un fichero (y no de probar un código).

Finalmente, vendría bien implementar un control para el caso en que no se pudieran abrir los ficheros, especialmente si es el usuario quien indicará el fichero que se quiere ordenar.

Saludos