Внешняя сортировка. 
Структуры и алгоритмы обработки данных

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

Основой большинства алгоритмов внешней сортировки является принцип слияния двух упорядоченных последовательностей в единый упорядоченный набор.

Например, пусть имеются две упорядоченные числовые последовательности: (5, 11, 17) и (8, 9, 19, 25).

Их слияние выполняется следующим образом:

• · сравниваются первые числа 5 и 8, наименьшее (5) помещается в выходной набор: (5)
• · сравниваются 11 и 8, наименьшее (8) — в выходной набор: (5, 8)
• · сравниваются 11 и 9, наименьшее (9) — в выходной набор: (5, 8, 9)
• · сравниваются 11 и 19, наименьшее (11) — в выходной набор: (5, 8, 9, 11)
• · сравниваются 17 и 19, наименьшее (17) — в вых. набор: (5, 8, 9, 11, 17)
• · остаток второй последовательности (19, 25) просто копируется в выходной набор с получением окончательного результата: (5, 8, 9, 11, 17, 19, 25)

В общем виде алгоритм слияния можно представить следующим образом. Пусть А={a_i} и B={b_j} - две исходные упорядоченные последовательности, R — результирующая последовательность.

• 1. сравниваем, а ₁ и b₁, если, а ₁ < b₁, то записываем, а ₁ в R, иначе — b₁ в R
• 2. если в уменьшившемся наборе остались числа, то сравниваем его минимальный элемент с минимальным элементом другого набора и записываем наименьший из них в R
• 3. повторяем шаг 2 до тех пор, пока не закончится какой-нибудь из наборов
• 4. как только заканчивается какой-нибудь набор, все оставшиеся элементы другой последовательности копируются в результирующий набор.

Алгоритм слияния можно использовать и для сортировки массивов, если последовательно применить его несколько раз ко все более длинным упорядоченным последовательностям. Для этого:

• 1. В исходном наборе выделяются две подряд идущие возрастающие подпоследовательности (серии)
• 2. Эти подпоследовательности (серии) сливаются в одну более длинную упорядоченную последовательность так, как описано выше
• 3. Шаги 1 и 2 повторяются до тех пор, пока не будет достигнут конец входного набора
• 4. Шаги 1−3 применяются к новому полученному набору, т. е. выделяются пары серий, которые сливаются в еще более длинные наборы, и т. д. до тех пор, пока не будет получена единая упорядоченная последовательность.

Пример. Пусть имеется входной неупорядоченный набор чисел:

24, 08, 13, 17, 06, 19, 20, 11, 07, 55, 33, 22, 18, 02, 40.

Этап 1. Выделяем в нем серии (показаны скобками) и попарно сливаем их:

• (24), (08, 13, 17), (06, 19, 20), (11), (07, 55), (33), (22), (18), (02, 40)
• (24) + (08, 13, 17) = (08, 13, 17, 24)
• (06, 19, 20) + (11) = (06, 11, 19, 20)
• (07, 55) + (33) = (07, 33, 55)
• (22) + (18) = (18, 22)

Новый набор чисел:

08, 13, 17, 24, 06, 11, 19, 20, 07, 33, 55, 18, 22, 02, 40.

Этап 2. Выделяем в новом наборе серии и попарно сливаем их (число серий уменьшилось):

• (08, 13, 17, 24), (06, 11, 19, 20), (07, 33, 55), (18, 22), (02, 40)
• (08, 13, 17, 24) + (06, 11, 19, 20) = (06, 08, 11, 13, 17, 19, 20, 24)
• (07, 33, 55) + (18, 22) = (07, 18, 22, 33, 55).

Новый набор:

06, 08, 11, 13, 17, 19, 20, 24, 07, 18, 22, 33, 55, 02, 40.

Этап 3. Выделяем в новом наборе серии (всего три) и сливаем их:

• (06, 08, 11, 13, 17, 19, 20, 24), (07, 18, 22, 33, 55), (02, 40)
• (06, 08, 11, 13, 17, 19, 20, 24) + (07, 18, 22, 33, 55) = (06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55).

Новый набор и его две серии:

(06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55), (02, 40).

Этап 4. После слияния этих двух серий получим полностью упорядоченный набор:

02, 06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 40, 55.

Данный метод сортировки называется естественным слиянием. Его особенностью является то, что для его реализации на каждом шаге достаточно сравнивать только два элемента. Именно это позволяет хранить все основные элементы в дисковых файлах, загружая в ОП только небольшое число элементов из каждой серии.

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

Для устранения этого недостатка можно поступить следующим образом:

• · исходный сверхбольшой набор данных разделяется на отдельные фрагменты такого размера, чтобы каждый фрагмент мог целиком разместиться в ОП
• · каждый фрагмент отдельно загружается в ОП и сортируется каким-нибудь классическим улучшенным методом (например — алгоритмом быстрой сортировки)
• · каждый отсортированный фрагмент рассматривается как серия и сохраняется во вспомогательном файле; в простейшем случае достаточно двух вспомогательных файлов, в которые серии сбрасываются поочередно (нечетные серии — в один файл (A), четные — в другой (B)).

Эти действия носят подготовительный характер.

После этого начинается 2-ой этап сортировки:

• · выполняется объединение первых серий из разных файлов, т. е. серий 1 и 2, и результат записывается в третий вспомогательный файл С.
• · выполняется объединение вторых серий из разных файлов, т. е. серий 3 и 4, и результат записывается во вспомогательный файл D.
• · выполняется объединение третьих серий из разных файлов, т. е. серий 5 и 6, и результат записывается опять в файл С.
• · серии 7 и 8 после объединения записываются в файл D и т. д.

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

Для программной реализации данного метода сортировки необходимы:

• · достаточно большой массив в ОП для реализации 1-го этапа
• · пять файлов, из которых один исходный и 4 вспомогательных.

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

Наоборот, если требуется ускорить сортировку за счет дополнительной дисковой памяти, то вместо 4-х вспомогательных файлов можно использовать 6,8,10 и т. д. Ускорение работы происходит за счет того, что объединяются не 2 серии, а 3, 4 или 5 и т. д.