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) Каким методом может быть выполнена внешняя сортировка данных без использования дополнительных файлов?