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

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

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

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

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

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

/* Дисковая сортировка структур типа 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, понадобилось бы еще одно перемещение головки.

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