Re: Алгоритмы сортировк

From

Anatoly Saveliev ()

To

Vlad Salikov

Date

2002-12-13T08:42:59Z

Area

RU.ALGORITHMS

From: Anatoly Saveliev <Anatoly.Saveliev@ksu.ru>

Vlad Salikov wrote:

> Имеем dbf-файл (телефонный справочник с полями TEL, FIO, ADRES) размером
> 2,8Мб. Имеется свободная оперативная память размером около 700Кб. Задача

> Создать-то я их создам, но как их сортировать в условиях острой нехватки
> памяти? На диске - долго, хочется побыстрее, да и винт жалко. :^)

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

Число слияний - log2(число кусков), так что и диск не вспотеет.

Наконец, если вывалить в виде текстовой таблицы в файл, то программа
sort от de'Billa сделает все описанное сама.


Анатолий Савельев
Казанский университет
--- ifmail v.2.15dev5
 * Origin: MELT InterNetNews site (2:5020/400)