Сортировка в одном файле
Алгоритм упорядочения данных в одном файле (то есть на месте) получается естественным обобщением метода пузырька. Роль такого пузырька играет порция данных, в которой постепенно накапливаются записи с наибольшими (или наименьшими) значениями ключа. Величина порции составляет половину выделенного для сортировки объема оперативной памяти. Допустим, что файл разбивается на N порций (зон).
В начале процесса в память считываются две первые порции (зоны) данных и упорядочиваются там как единый массив, после чего половина массива с меньшими значениями ключа (назовем ее "нижней") записывается во вторую зону. На освободившееся место считывается третья зона, содержимое памяти вновь сортируется каким либо методом внутренней сортировки, и нижняя половина записывается в третью зону. Процесс повторяется для всех зон до N-1 включительно. После считывания N-й зоны и внутренней сортировки уже верхняя половина (пузырек) записывается в N-ю зону. Таким образом ключи последней зоны уже заняли свое окончательное положение в файле. Процесс повторяется для оставшихся N-1 зоны , затем для оставшихся N-2 зоны и т.д.
Ниже приведен текст функции, реализующей алгоритм.
int BubbleExternSort(char *FileName, int RecLen,
int (*cmp)(const void *r1, const void *r2), int MemSize){
// Внешняя сортировка пузырьком
// FileName - имя бинарного файла, содержащего таблицу
// RecLen - длина записи
// cmp - функция, сравнивающая ключи записей
// возвращает -1,0,1
// MemSize - размер оперативной памяти, который разрешено
// использовать для сортировки
// при нормальном завершении возвращает 0
// в противном случае - код ошибки
int h; // дескриптор файла
long FileSize; // размер файла
unsigned long nZon; // число зон
int ZonSize; // размер зоны в байтах
Int i;
char *Buffer; // память для сортировки
Дата добавления: 2014-12-02; просмотров: 842;