Сортировка в одном файле

Каскадное слияние

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

Проход 2, например, поучается выполнением 5-путеврго слияния с F1…F5 на F6, пока не опустеет F5, затем 4-путевого слияния с F1…F4 на F5, 3-путевого с F1, F2, F3 на F4, 2-путевого с F1, F2 на F3, и, наконец, однопутевого (копирования) – с F1 на F2. Подробно второй проход представлен в таблице:

Ясно, что операция копирования излишня и оставлена в описании алгоритма только для сохранения единообразия процесса.

Рассматривая процесс в обратном порядке, и игнорируя выходной файл, можно вывести точные распределения отрезков по файлам на любом этапе:

Числа в распределении носят название каскадных.

Алгоритм упорядочения данных в одном файле (то есть на месте) получается естественным обобщением метода пузырька. Роль такого пузырька играет порция данных, в которой постепенно накапливаются записи с наибольшими (или наименьшими) значениями ключа. Величина порции составляет половину выделенного для сортировки объема оперативной памяти. Допустим, что файл разбивается на 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; // память для сортировки

unsigned long izon, jzon;

int nByte;

h=_rtl_open(FileName, O_RDWR); // открытие бинарного файла

if(h<0) return 1; // не удалось открыть файл

FileSize=lseek(h,0L,SEEK_END);

if(RecLen*(FileSize/RecLen)!=FileSize) {

close(h); // размер файла не кратен длине записи

return 2;

}

ZonSize=(MemSize/RecLen/2)*RecLen;

nZon=FileSize/ZonSize;

if(nZon*ZonSize!=FileSize){ // последняя зона неполная

nZon++;

}

if(ZonSize<RecLen){

close(h);

return 3; // мало дали памяти

}

Buffer=new char[2*ZonSize+1];

if(Buffer==NULL) {

close(h);

return 4; // нет памяти

}

Buffer[2*ZonSize]=0;

for(izon=nZon-1; izon>1; izon--){ // проходы по файлу

// izon - число зон в данном проходе

// читать первые две зоны

lseek(h, 0L, SEEK_SET);

nByte=_rtl_read(h, Buffer, 2*ZonSize);

for(jzon=0; jzon < izon-1; jzon++){

// сортировать

qsort(Buffer, nByte/RecLen, RecLen, cmp);

// нижнюю половину - в зону jzon

lseek(h, jzon*ZonSize, SEEK_SET);

_rtl_write(h, Buffer, ZonSize);

// подкачать следующую зону

lseek(h, (jzon+2)*ZonSize, SEEK_SET);

nByte=_rtl_read(h, Buffer, ZonSize);

// если прочитано меньше ZonSize,

// то верхнюю половину сдвинуть вниз

// на ZonSize-nByte вплотную к нижней

if(nByte < ZonSize){

for(i=0; i<ZonSize; i++){

Buffer[nByte+i]=Buffer[ZonSize+i];

}

}

nByte+=ZonSize;

}

// переписать пузырек

qsort(Buffer, nByte/RecLen, RecLen, cmp);

lseek(h, (izon-1)*ZonSize, SEEK_SET);

_rtl_write(h, Buffer, nByte);

}

// две первых зоны

lseek(h, 0L, SEEK_SET);

nByte=_rtl_read(h, Buffer, 2*ZonSize);

qsort(Buffer, nByte/RecLen, RecLen, cmp);

lseek(h,0L,SEEK_SET);

_rtl_write(h, Buffer, nByte);

delete [] Buffer;

close(h);

return 0;

}

Аналогично методу пузырька для внутренней сортировки, число проходов по данным ~N², где N – число зон.

Контрольные вопросы

1) Какова оценка времени поиска записи в сортированной таблице?

2) Какие проблемы вызывают операции вставки и удаления для сортированной таблицы?

3) Какова нижняя граница времени работы сортировки, основанной на сравнениях ключей?

4) Перечислите известные вам методы внутренней сортировки.

5) Дайте описание алгоритмов внутренней сортировки, имеющих время работы порядка

6) В чем заключается принципиальное отличие внешней сортировки от внутренней?

7) Опишите метод, позволяющий порождать сортированные отрезки длины большей, чем объем оперативной памяти, отведенной для этого.

8) За счет чего удается избежать операций копирования при использовании Фибоначчиева слияния?

9) Каким методом может быть выполнена внешняя сортировка данных без использования дополнительных файлов?