6 Ordenar ficheros de acceso aleatorio

Cuando trabajemos con ficheros de acceso secuencial con tamaño de registro constante, podremos aplicar los mismos algoritmos de ordenación que con tablas en memoria, ya que es posible acceder a cada registro para lectura y escritura.

En el caso de ficheros de acceso aleatorio con tamaño de registro variable, los trataremos como si fueran secuenciales.

Algoritmo Quicksort

Por supuesto, hay que elegir un algoritmo que impleque un mínimo de lecturas y escrituras en el fichero, y preferentemente, que éstas operaciones estén los más próximas posible entre si. Resulta muy costoso, en términos de tiempo de ejecución, hacer muchas lecturas y escrituras en disco, y más si los puntos donde se realizan están muy separados entre ellos.

Como ejemplo, usaremos el algoritmo de ordenación quicksort, adaptándolo para ordenar ficheros.

Usaremos el programa de ejemplo que usamos para los archivos de acceso aleatorio "alea.cpp". Y añadiremos una nueva opción para ordenar el archivo.

Ejemplo

// alea2.c: Ejemplo de ficheros de acceso aleatorio.
// Incluye la opción de ordenar el archivo.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct stRegistro {
   char valido;  // Campo que indica si el registro es valido S->Válido, N->Inválido
   char nombre[34];
   int dato[4];
};

int Menu();
void Leer(struct stRegistro *reg);
void Mostrar(struct stRegistro *reg);
void Listar(long n, struct stRegistro *reg);
long LeeNumero();
void Empaquetar(FILE **fa);
void Ordenar(FILE *fa);
void Intercambia(FILE *fa, long iz, long de);
char *LeeCampo(FILE *fa, long n, char *buf);
void QuickSort(FILE *fa, long inicio, long final);

int main()
{
   struct stRegistro reg;
   FILE *fa;
   int opcion;
   long numero;
   fa = fopen("alea.dat", "r+b");          // Este modo permite leer y escribir
   if(!fa) fa = fopen("alea.dat", "w+b");  // si el fichero no existe, lo crea.
   do {
      opcion = Menu();
      switch(opcion) {
         case '1': // Añadir registro
            Leer(&reg);
            // Insertar al final:
            fseek(fa, 0, SEEK_END);
            fwrite(&reg, sizeof(struct stRegistro), 1, fa);
            break;
         case '2': // Mostrar registro
            system("cls");
            printf("Mostrar registro: ");
            numero = LeeNumero();
            fseek(fa, numero*sizeof(struct stRegistro), SEEK_SET);
            fread(&reg, sizeof(struct stRegistro), 1, fa);
            Mostrar(&reg);
            break;
         case '3': // Eliminar registro
            system("cls");
            printf("Eliminar registro: ");
            numero = LeeNumero();
            fseek(fa, numero*sizeof(struct stRegistro), SEEK_SET);
            fread(&reg, sizeof(struct stRegistro), 1, fa);
            reg.valido = 'N';
            fseek(fa, numero*sizeof(struct stRegistro), SEEK_SET);
            fwrite(&reg, sizeof(struct stRegistro), 1, fa);
            break;
         case '4': // Mostrar todo
            rewind(fa);
            numero = 0;
            system("cls");
            printf("Nombre                             Datos\n");
            while(fread(&reg, sizeof(struct stRegistro), 1, fa))
               Listar(numero++, &reg);
            system("PAUSE");
            break;
         case '5': // Eliminar marcados
            Empaquetar(&fa);
            break;
         case '6': // Ordenar
            Empaquetar(&fa);
            Ordenar(fa);
            break;
      }
   } while(opcion != '0');
   fclose(fa);
   return 0;
}

// Muestra un menú con las opciones disponibles y captura una opción del usuario
int Menu()
{
   char resp[20];
   do {
      system("cls");
      printf("MENU PRINCIPAL\n");
      printf("--------------\n\n");
      printf("1- Insertar registro\n");
      printf("2- Mostrar registro\n");
      printf("3- Eliminar registro\n");
      printf("4- Mostrar todo\n");
      printf("5- Eliminar registros marcados\n");
      printf("6- Ordenar fichero\n");
      printf("0- Salir\n");
      fgets(resp, 20, stdin);
   } while(resp[0] < '0' && resp[0] > '6');
   return resp[0];
}

// Permite que el usuario introduzca un registro por pantalla
void Leer(struct stRegistro *reg)
{
   int i;
   char numero[6];
   system("cls");
   printf("Leer registro:\n\n");
   reg->valido = 'S';
   printf("Nombre: ");
   fgets(reg->nombre, 34, stdin);
   // la función fgets captura el retorno de línea, hay que eliminarlo:
   for(i = strlen(reg->nombre)-1; i && reg->nombre[i] < ' '; i--)
      reg->nombre[i] = 0;
   for(i = 0; i < 4; i++) {
      printf("Dato[%1d]: ", i);
      fgets(numero, 6, stdin);
      reg->dato[i] = atoi(numero);
   }
}

// Muestra un registro en pantalla, si no está marcado como borrado
void Mostrar(struct stRegistro *reg)
{
   int i;
   system("cls");
   if(reg->valido == 'S') {
      printf("Nombre: %s\n", reg->nombre);
      for(i = 0; i < 4; i++)
         printf("Dato[%1d]: %d\n", i, reg->dato[i]);
   }
   system("PAUSE");
}

// Muestra un registro por pantalla en forma de listado,
// si no está marcado como borrado
void Listar(long n, struct stRegistro *reg)
{
   int i;
   if(reg->valido == 'S') {
      printf("[%6ld] %-34s", n, reg->nombre);
      for(i = 0; i < 4; i++) printf(", %4d", reg->dato[i]);
      printf("\n");
   }
}

// Lee un número suministrado por el usuario
long LeeNumero()
{
   char numero[6];
   fgets(numero, 6, stdin);
   return atoi(numero);
}

// Elimina los registros marcados como borrados
void Empaquetar(FILE **fa)
{
   FILE *ftemp;
   struct stRegistro reg;

   ftemp = fopen("alea.tmp", "wb");
   rewind(*fa);
   while(fread(&reg, sizeof(struct stRegistro), 1, *fa))
      if(reg.valido == 'S')
         fwrite(&reg, sizeof(struct stRegistro), 1, ftemp);
   fclose(ftemp);
   fclose(*fa);
   remove("alea.bak");
   rename("alea.dat", "alea.bak");
   rename("alea.tmp", "alea.dat");
   *fa = fopen("alea.dat", "r+b");
}

void Ordenar(FILE *fa)
{
   long nRegs;
   fseek(fa, 0, SEEK_END);
   nRegs = ftell(fa)/sizeof(struct stRegistro);
   QuickSort(fa, 0L, nRegs-1);
}

void QuickSort(FILE *fa, long inicio, long final)
{
   long iz, de;
   char mitad[34];
   static char cad[34];

   iz = inicio;
   de = final;
   strcpy(mitad, LeeCampo(fa, (iz+de)/2, cad));
   do {
      while(strcmp(LeeCampo(fa, iz, cad), mitad) < 0 && iz < final) iz++;
      while(strcmp(mitad, LeeCampo(fa, de, cad)) < 0 && de > inicio) de--;
      if(iz < de) Intercambia(fa, iz, de);
      if(iz <= de) {
         iz++;
         de--;
      }
   } while(iz <= de);
   if(inicio < de) QuickSort(fa, inicio, de);
   if(iz < final) QuickSort(fa, iz, final);
}

char *LeeCampo(FILE *fa, long n, char *buf)
{
   struct stRegistro reg;
   fseek(fa, n*sizeof(struct stRegistro), SEEK_SET);
   fread(&reg, sizeof(struct stRegistro), 1, fa);
   strcpy(buf, reg.nombre);
   return buf;
}

void Intercambia(FILE *fa, long iz, long de)
{
   struct stRegistro reg1, reg2;
   fseek(fa, iz*sizeof(struct stRegistro), SEEK_SET);
   fread(&reg1, sizeof(struct stRegistro), 1, fa);
   fseek(fa, de*sizeof(struct stRegistro), SEEK_SET);
   fread(&reg2, sizeof(struct stRegistro), 1, fa);
   fseek(fa, iz*sizeof(struct stRegistro), SEEK_SET);
   fwrite(&reg2, sizeof(struct stRegistro), 1, fa);
   fseek(fa, de*sizeof(struct stRegistro), SEEK_SET);
   fwrite(&reg1, sizeof(struct stRegistro), 1, fa);
}

El algoritmo que hemos usado es bastante bueno para ordenar ficheros, ya que requiere muy pocos intercambios de registros, pero de todos modos, con ficheros grandes puede ser un proceso muy lento. En general es preferible no ordenar los ficheros, salvo que sea muy necesario.

Veamos ahora un ejemplo basado en streams para C++:

// alea2.cpp: Ejemplo de ficheros de acceso aleatorio.
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <cstring>

using namespace std;

// Funciones auxiliares:
int Menu();
long LeeNumero();

// Clase registro.
class Registro {
  public:
   Registro(char *n=NULL, int d1=0, int d2=0, int d3=0, int d4=0) : valido('S') {
     if(n) strcpy(nombre, n); else strcpy(nombre, "");
     dato[0] = d1;
     dato[1] = d2;
     dato[2] = d3;
     dato[3] = d4;
   }
   void Leer();
   void Mostrar();
   void Listar(long n);

   const bool Valido() { return valido == 'S'; }
   const char *Nombre() { return nombre; }
  private:
   char valido;  // Campo que indica si el registro es válido
                 // S->Válido, N->Inválido
   char nombre[34];
   int dato[4];
};

// Implementaciones de clase Registro:
// Permite que el usuario introduzca un registro por pantalla
void Registro::Leer() {
   system("cls");
   cout << "Leer registro:" << endl << endl;
   valido = 'S';
   cout << "Nombre: ";
   cin.getline(nombre, 34);
   for(int i = 0; i < 4; i++) {
      cout << "Dato[" << i << "]: ";
      dato[i] = LeeNumero();
   }
}

// Muestra un registro en pantalla, si no está marcado como borrado
void Registro::Mostrar()
{
   system("cls");
   if(Valido()) {
      cout << "Nombre: " << nombre << endl;
      for(int i = 0; i < 4; i++)
         cout << "Dato[" << i << "]: " << dato[i] << endl;
   }
   cout << "Pulsa una tecla";
   cin.get();
}

// Muestra un registro por pantalla en forma de listado,
// si no está marcado como borrado
void Registro::Listar(long n) {
   int i;
   if(Valido()) {
      cout << "[" << setw(6) << n << "] ";
      cout << setw(34) << nombre;
      for(i = 0; i < 4; i++)
         cout << ", " << setw(4) << dato[i];
      cout << endl;
   }
}

// Clase Datos, almacena y trata los datos.
class Datos :public fstream {
  public:
   Datos() : fstream("alea.dat", ios::in | ios::out | ios::binary) {
      if(!good()) {
         open("alea.dat", ios::in | ios::out | ios::trunc | ios::binary);
         cout << "fichero creado" << endl;
         cin.get();
      }
   }
  ~Datos() {
     Empaquetar();
   }
   void Guardar(Registro &reg);
   bool Recupera(long n, Registro &reg);
   void Borrar(long n);
   void Ordenar();

  private:
   void Empaquetar();
   void Intercambia(long iz, long de);
   char *LeeCampo(long n, char *buf);
   void QuickSort(long inicio, long final);
};

// Implementación de la clase Datos.
void Datos::Guardar(Registro &reg) {
   // Insertar al final:
   clear();
   seekg(0, ios::end);
   write(reinterpret_cast<char *> (&reg), sizeof(Registro));
   cout << reg.Nombre() << endl;
}

bool Datos::Recupera(long n, Registro &reg) {
   clear();
   seekg(n*sizeof(Registro), ios::beg);
   read(reinterpret_cast<char *> (&reg), sizeof(Registro));
   return gcount() > 0;
}

// Marca el registro como borrado:
void Datos::Borrar(long n) {
   char marca;

   clear();
   marca = 'N';
   seekg(n*sizeof(Registro), ios::beg);
   write(&marca, 1);
}

// Elimina los registros marcados como borrados
void Datos::Empaquetar() {
   ofstream ftemp("alea.tmp", ios::out);
   Registro reg;

   clear();
   seekg(0, ios::beg);
   do {
      read(reinterpret_cast<char *> (&reg), sizeof(Registro));
      if(gcount() > 0 && reg.Valido())
         ftemp.write(reinterpret_cast<char *> (&reg), sizeof(Registro));
   } while (gcount() > 0);
   ftemp.close();
   close();
   remove("alea.bak");
   rename("alea.dat", "alea.bak");
   rename("alea.tmp", "alea.dat");
   open("alea.dat", ios::in | ios::out | ios::binary);
}

// Ordenar el fichero:
void Datos::Ordenar()
{
   long nRegs;

   Empaquetar();

   clear();
   seekg(0, ios::end);
   nRegs = tellg()/sizeof(Registro);
   QuickSort(0, nRegs-1);
}

// Funciones auxiliares para ordenar
void Datos::QuickSort(long inicio, long final)
{
   long iz, de;
   char mitad[34];
   static char cad[34];

   iz = inicio;
   de = final;
   strcpy(mitad, LeeCampo((iz+de)/2, cad));
   do {
      while(strcmp(LeeCampo(iz, cad), mitad) < 0 && iz < final) iz++;
      while(strcmp(mitad, LeeCampo(de, cad)) < 0 && de > inicio) de--;
      if(iz < de) Intercambia(iz, de);
      if(iz <= de) {
         iz++;
         de--;
      }
   } while(iz <= de);
   if(inicio < de) QuickSort(inicio, de);
   if(iz < final) QuickSort(iz, final);
}

char* Datos::LeeCampo(long n, char *buf)
{
   Registro reg;

   seekg(n*sizeof(Registro), ios::beg);
   read(reinterpret_cast<char *> (&reg), sizeof(Registro));
   strcpy(buf, reg.Nombre());
   return buf;
}

void Datos::Intercambia(long iz, long de)
{
   Registro reg1, reg2;

   seekg(iz*sizeof(Registro), ios::beg);
   read(reinterpret_cast<char *> (&reg1), sizeof(Registro));
   seekg(de*sizeof(Registro), ios::beg);
   read(reinterpret_cast<char *> (&reg2), sizeof(Registro));
   seekp(iz*sizeof(Registro), ios::beg);
   write(reinterpret_cast<char *> (&reg2), sizeof(Registro));
   seekp(de*sizeof(Registro), ios::beg);
   write(reinterpret_cast<char *> (&reg1), sizeof(Registro));
}

int main()
{
   Registro reg;
   Datos datos;
   int opcion;
   long numero;
   do {
      opcion = Menu();
      switch(opcion) {
         case '1': // Añadir registro
            reg.Leer();
            datos.Guardar(reg);
            break;
         case '2': // Mostrar registro
            system("cls");
            cout << "Mostrar registro: ";
            numero = LeeNumero();
            if(datos.Recupera(numero, reg))
               reg.Mostrar();
            break;
         case '3': // Eliminar registro
            system("cls");
            cout <<  "Eliminar registro: ";
            numero = LeeNumero();
            datos.Borrar(numero);
            break;
         case '4': // Mostrar todo
            numero = 0;
            system("cls");
            cout << "Nombre                             Datos" << endl;
            while(datos.Recupera(numero, reg)) reg.Listar(numero++);
            cout << "pulsa return";
            cin.get();
            break;
         case '5': // Ordenar
            datos.Ordenar();
            break;
      }
   } while(opcion != '0');
   return 0;
}

// Muestra un menú con las opciones disponibles y captura una opción del usuario
int Menu()
{
   char resp[20];
   do {
      system("cls");
      cout << "MENU PRINCIPAL" << endl;
      cout << "--------------" << endl << endl;
      cout << "1- Insertar registro" << endl;
      cout << "2- Mostrar registro" << endl;
      cout << "3- Eliminar registro" << endl;
      cout << "4- Mostrar todo" << endl;
      cout << "5- Ordenar" << endl;
      cout << "0- Salir" << endl;
      cin.getline(resp, 20);
   } while(resp[0] < '0' && resp[0] > '5');
   return resp[0];
}

// Lee un número suministrado por el usuario
long LeeNumero()
{
   char numero[6];
   fgets(numero, 6, stdin);
   return atoi(numero);
}