22. Внешняя сортировка: сортировка разделительным методом ПАРОМСОРТ. Временная сложность алгоритма. Рекомендации по использованию внешней сортировки.

 

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

            Процесс сортировки обменами не требует дополнительного пространства и весьма эффективно использует всю предоставленную оперативную память, которая выполняет роль парома при перемещении записей от одного конца файла (“берега”) к другому: “малые” записи, т.е. записи с меньшими ключами, доставляются к “левому” берегу (в начало файла); “большие” записи, т.е. записи с большими ключами,  - к “правому” берегу (в конец файла).

            Познакомимся с паромной сортировкой подробнее. Пусть в нашем распоряжении имеется К сегментов оперативной памяти; К>1. Заполняем их данными, считывая начало файла, либо, на более поздних этапах, начало разделяемой части файла. В оперативной памяти начинаем разделение на “большие” и “малые” записи. При этом для накопления “меньших” записей используем только первый сегмент оперативной памяти, для накопления “больших” записей - остальные К-1 сегменты. Это связано с тем, что мы находимся у “левого” берега. Когда в первом сегменте останутся одни “меньшие” записи, разгружаем его в файл, а из файла передаем в первый сегмент следующую порцию записей и т.д.

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

            В этот момент первый сегмент должен быть свободен, иначе не “разгрузить” паром: сначала освобождаем окончание файла, передавая его записи в первый сегмент. Теперь, сегмент за сегментом, переписываем “большие” записи в файл, параллельно заполняя сегменты новыми записями.

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

            Процесс продолжается до тех пор, пока все “малые” и все “большие” записи не будут сгруппированы, что позволит определить точку раздела между группами. Если размер группы еще не позволяет применить к ней внутреннюю сортировку, то к ней рекурсивно применяем ПАРОМСОРТ.

            К достоинствам этого метода относят высокое быстродействие (даже неудачный выбор на каждом шаге опорного ключа способен лишь увеличить время внутренней сортировки, доля которой в общих временных затратах весьма мала) и предельную компактность, т.к. он работает в пределах пространства, занятого файлом. Метод ПАРОМСОРТ рекомендуется использовать для средних и больших файлов.