Сортировка дисковых файлов с произвольной выборкой

Дисковые файлы бывают двух типов: с последовательной выборкой (доступом) и с произвольной выборкой. Если дисковый файл любого типа достаточно мал, его можно считать в память и отсортировать одной из процедур сортировки массивов, представленных выше. Однако многие дисковые файлы слишком велики для того, чтобы сортировать их в памяти, а поэтому требуют особенных приемов сортировки. Многие приложения баз данных работают с файлами с произвольной выборкой. В данном разделе показан один способ сортировки таких файлов.

Дисковые файлы с произвольной выборкой доступа имеют два больших преимущества перед файлами с последовательной выборкой. Во-первых, с ними легко работать. Для обновления информации не нужно копировать весь список. Во-вторых, их можно рассматривать как очень большой массив на диске, что значительно упрощает сортировку.

Тот факт, что файл с произвольной выборкой можно рассматривать как массив, означает, что к нему можно применить быструю сортировку лишь с небольшим количеством изменений. Вместо обращения к элементам массива по индексу, дисковая версия быстрой сортировки должна пользоваться функцией fseek(), чтобы найти соответствующую запись на диске.

В каждой реальной ситуации сортировка определяется конкретной структурой сортируемых данных и ключом сортировки. Тем не менее, общую идею сортировки дисковых файлов с произвольной выборкой можно понять на примере короткой программы, сортирующей структуры типа address — почтовые структуры, описанные ранее. Эта программа, приведенная ниже, сначала создает дисковый файл, содержащий неупорядоченные адреса. Затем она сортирует этот файл. Количество адресов, подлежащих сортировке, указано константой NUM_ELEMENTS (которая равна 4 в данной программе). Однако в реальной жизни количество записей придется отслеживать динамически. Поэкспериментируйте с этой программой самостоятельно, пробуя различные типы структур, содержащие разнообразные данные:

/* Дисковая сортировка структур типа address. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NUM_ELEMENTS 4  /* Количество элементов - произвольное
                           число, которое должно определяться
                           динамически для каждого списка. */

struct address {
  char name[30];
  char street[40];
  char city[20];
  char state[3];
  char zip[11];
} ainfo;

struct address addrs[NUM_ELEMENTS] = {
  "A. Alexander", "101 1st St", "Olney", "Ga", "55555",
  "B. Bertrand", "22 2nd Ave", "Oakland", "Pa", "34232",
  "C. Carlisle", "33 3rd Blvd", "Ava", "Or", "92000",
  "D. Dodger", "4 Fourth Dr", "Fresno", "Mi", "45678"
};

void quick_disk(FILE *fp, int count);
void qs_disk(FILE *fp, int left, int right);
void swap_all_fields(FILE *fp, long i, long j);
char *get_zip(FILE *fp, long rec);

int main(void)
{
  FILE *fp;

  /* сначала создадим файл с данными, подлежащий сортировке */
  if((fp=fopen("mlist", "wb"))==NULL) {
    printf("Невозможно отрыть файл на запись.\n");
    exit(1);
  }
  printf("Запись неупорядоченных данных в дисковый файл.\n");
  fwrite(addrs, sizeof(addrs), 1, fp);
  fclose(fp);

  /* теперь отсортируем файл */
  if((fp=fopen("mlist", "rb+"))==NULL) {
    printf("Невозможно отрыть файл на чтение/запись.\n");
    exit(1);
  }

  printf("Сортировка диского файла.\n");
  quick_disk(fp, NUM_ELEMENTS);
  fclose(fp);
  printf("Файл отсортирован.\n");

  return 0;
}

/* Быстрая сортировка файлов. */
void quick_disk(FILE *fp, int count)
{
  qs_disk(fp, 0, count-1);
}

void qs_disk(FILE *fp, int left, int right)
{
  long int i, j;
  char x[100];

  i = left; j = right;

  strcpy(x, get_zip(fp, (long)(i+j)/2)); /* получить средний почтовый
                                            индекс */

  do {
    while((strcmp(get_zip(fp,i),x) < 0) && (i < right)) i++;
    while((strcmp(get_zip(fp,j),x) > 0) && (j > left)) j--;

    if(i <= j) {
      swap_all_fields(fp, i, j);
      i++; j--;
    }
  } while(i <= j);

  if(left < j) qs_disk(fp, left, (int) j);
  if(i < right) qs_disk(fp, (int) i, right);
}

void swap_all_fields(FILE *fp, long i, long j)
{
  char a[sizeof(ainfo)], b[sizeof(ainfo)];

  /* считать в память записи i и j */
  fseek(fp, sizeof(ainfo)*i, SEEK_SET);
  fread(a, sizeof(ainfo), 1, fp);

  fseek(fp, sizeof(ainfo)*j, SEEK_SET);
  fread(b, sizeof(ainfo), 1, fp);

  /* потом записать их на диск, поменяв местами */
  fseek(fp, sizeof(ainfo)*j, SEEK_SET);
  fwrite(a, sizeof(ainfo), 1, fp);
  fseek(fp, sizeof(ainfo)*i, SEEK_SET);
  fwrite(b, sizeof(ainfo), 1, fp);
}

/* Получение указателя на почтовый код записи */
char *get_zip(FILE *fp, long rec)
{
  struct address *p;

  p = &ainfo;

  fseek(fp, rec*sizeof(ainfo), SEEK_SET);
  fread(p, sizeof(ainfo), 1, fp);

  return ainfo.zip;
}

Как вы, наверное, уже заметили, для сортировки адресных записей пришлось написать две вспомогательные функции. Во фрагменте сравнения используется функция get_zip(), возвращающая указатель на поле zip сравниваемых записей. Функция swap_all_fields() выполняет обмен данных двух записей. Порядок операций чтения и записи оказывает большое влияние на скорость выполнения сортировки. При обмене двух записей программа перемещает указатель текущей записи в файле сначала на запись i, а потом на запись j. Пока головка диска находится над записью j, записываются данные записи j. Это значит, что в этот момент головку не придется перемещать на большое расстояние. Если бы код был составлен так, что первой записывалась бы запись i, понадобилось бы еще одно перемещение головки.