Дисковые файлы бывают двух типов: с последовательной выборкой (доступом) и с произвольной выборкой. Если дисковый файл любого типа достаточно мал, его можно считать в память и отсортировать одной из процедур сортировки массивов, представленных выше. Однако многие дисковые файлы слишком велики для того, чтобы сортировать их в памяти, а поэтому требуют особенных приемов сортировки. Многие приложения баз данных работают с файлами с произвольной выборкой. Рассмотрим один способ сортировки таких файлов.
Дисковые файлы с произвольной выборкой доступа имеют два больших преимущества перед файлами с последовательной выборкой. Во-первых, с ними легко работать. Для обновления информации не нужно копировать весь список. Во-вторых, их можно рассматривать как очень большой массив на диске, что значительно упрощает сортировку.
Тот факт, что файл с произвольной выборкой можно рассматривать как массив, означает, что к нему можно применить
быструю сортировку лишь с небольшим количеством изменений. Вместо обращения к элементам массива по индексу, дисковая версия быстрой сортировки должна пользоваться функцией
fseek(), чтобы найти соответствующую запись на диске.
В каждой реальной ситуации сортировка определяется конкретной структурой сортируемых данных и ключом сортировки. Тем не менее, общую идею сортировки дисковых файлов с произвольной выборкой можно понять на примере короткой программы, сортирующей структуры типа address — почтовые структуры, описанные ранее. Эта программа, приведенная ниже, сначала создает дисковый файл, содержащий неупорядоченные адреса. Затем она сортирует этот файл. Количество адресов, подлежащих сортировке, указано
константой NUM_ELEMENTS (которая равна 4 в данной программе). Однако в реальной жизни количество записей придется отслеживать динамически.
/* дисковая сортировка структур типа ddress. */ #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[ll];
} 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(l);
}
printf ("Запись неупорядоченных данных в дисковый файл.\n"); fwrite(addrs, sizeof(addrs), 1, fp);
fclose(fp);
/* теперь отсортируем файл */
if ( (fp=fopen("mlist", "rb+") )= =NULL) {
printf("Невозможно открыть файл на чтение/запись.\n");
exit(l);
}
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, понадобилось бы еще одно перемещение головки.
