Многопутевое слияние и выбор с замещением

Внешняя сортировка

Рассмотренные методы сортировки были рассчитаны на то, что таблица целиком помещается в оперативной памяти и в любой момент открыт доступ к любому элементу таблицы. Внешняя сортировка отличается тем, что время доступа к данным на внешних носителях чрезвычайно велико по сравнению с временем доступа к оперативной памяти.

Предположим, что нужно отсортировать таблицу из 5000
R₁-R₅₀₀₀ записей, а в оперативную память помещается не более 1000 записей. Решение может быть следующим – начать с внутренней сортировки каждого из 5 отрезков по 1000 записей, а затем слить полученные сортированные отрезки. Такой процесс – внутренняя сортировка с последующим внешним слиянием – является основой многих методов внешней сортировки.

В качестве введения рассмотрим метод, который можно назвать сбалансированным двухпутевым слиянием. Метод использует 4 файла. В первой фазе упорядоченные отрезки, получаемые внутренней сортировкой, помещаются поочередно в файлы 1 и 2 до тех пор, пока не исчерпаются входные данные. Начальная фаза распределения отрезков размещает пять отрезков следующим образом:

Файл 1: R_{1 –} R₁₀₀₀; R_{2001 –} R₃₀₀₀; R_{4001 –} R₅₀₀₀

Файл 2: R₁₀₀₁ – R₂₀₀₀; R₃₀₀₁ – R₄₀₀₀

Файл 3: пусто

Файл 4: пусто

Затем файлы 1 и 2 вновь позиционируем на начало и сливаем отрезки с этих файлов, получая отрезки вдвое более длинные, чем исходные. Эти отрезки попеременно записываются в файлы 3,4. Отрезок R_{4001 –} R₅₀₀₀ в файле 1 не имеет пары для слияния в файле 2. Неявно добавим для создания такой пары в файл 2 фиктивный отрезок длины 0. После первого прохода слияния получим:

Файл 1: пусто

Файл 2: пусто

Файл 3: R_{1 –} R₂₀₀₀; R_{4001 –} R₅₀₀₀

Файл 4: R_{2001 –} R₄₀₀₀

Применив тот же алгоритм к файлам 3,4, в файлах 1,2 получим результат:

Файл 1: R_{1 –} R₄₀₀₀

Файл 2: R_{4001 –} R₅₀₀₀

Наконец, после последнего прохода в файле 3 получим R₁ – R₅₀₀₀, и сортировка завершена.

Аналогично можно рассмотреть 3-х и более – путевое слияние. Пусть для сортировки выделено N файлов. Разделим их на 2 части – в одной M файлов, в другой - N-M файлов. Распределим исходные отрезки по возможности более равномерно по M файлам первой части и выполним M-путевое слияние, помещая результат слияния поочередно в оставшиеся N-M файлов. Затем выполним N-M – путевое слияние, помещая результаты слияния в файлы первой части.

Рассмотрим процесс порождения начальных отрезков, которые затем подвергаются слиянию. Пусть имеется Р возрастающих отрезков. Очевидным способом их слияния является следующий: из первых ключей каждого отрезка выбрать минимальный, соответствующую запись передать на выход и исключить из входных данных, затем этот процесс повторяется. Если Р велико, то целесообразно использовать дерево выбора из Р элементов. Пример 4-х путевого слияния изображен на рис. 39.

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

Пример. Пусть исходная последовательность ключей:
2 7 12 3 8 9 4 1 5 11 10 6 и Р=4

Процесс вывода начальных сортированных отрезков иллюстрируется таблицей:

В скобки заключены ключи, не участвующие в дальнейшем выборе. Таким путем удается получить упорядоченные последовательности длиннее Р, что важно, так как время внешней сортировки слиянием в значительной мере зависит от числа начальных отрезков. Э.Ф.Мур предложил изящный способ доказательства того, что средняя длина порождаемого отрезка равна 2Р, проведя аналогию со снегоочисти­телем, движущимся по кругу. Пусть на кольцевую дорогу непре­рыв­но падают снежинки (записи). Снежинки исчезают из системы (запи­си выводятся), когда они сбрасываются за пределы дороги. Точки дороги обозначаются вещественными числами x (0 £ x £1). Снежинка, падающая в точку х, соответствует входной записи с ключом х, а снегоочиститель имитирует процесс вывода. В установившемся режиме общее число снежинок на дороге в точности равно Р. Каждый раз, когда снегоочиститель проходит точку 0, заканчивается формирование нового отрезка. На рис.40 изображено поперечное сечение дороги, когда система находится в

Рис. 39 Аналогия со снегоочистителем

Из рисунка видно, что количество снега, удаляемого за один оборот, вдвое превосходит количество снега, присутствующего на дороге в любой момент.