Слияние упорядоченных последовательностей

К последовательному файлу нельзя непосредственно применить метод внутренней сортировки (сортировки массивов). Это объясняется тем, что в последовательном файле в каждый момент имеется доступ только к одному элементу. Это строгое ограничение, по сравнению с возможностями, которые даёт массив, поэтому для файлов приходится применять другие методы сортировки.

Разумеется, в этом случае, когда размер файла не велик и объём оперативной памяти достаточен для его размещения, можно прочитать файл в память, отсортировать полученный массив одним из методов внутренней сортировки, а затем отсортированный массив записать в файл. Однако, это не является типичным случаем; более того, в системах обработки данных такая ситуация встречается крайне редко.

Далее мы рассмотрим общий случай, когда сортируемый файл имеет объём значительно больше, чем объём доступный оперативной памяти. Такой файл сортируется поэтапно.

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

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

Пусть даны две упорядоченные последовательности (файл) А и В со следующими значениями числовых ключей:

А: 06 12 18 42 44 56

В: 07 14 15 17 19

Читаем первые элементы каждого из файлов, сравниваем их и записываем меньший элемент в выходной файл С, а на его место читаем следующий элемент из соответствующего файла. После этой операции имеем следующее (элементы, прочитанные в память, подчёркнуты):

А: 12 18 42 44 55

В: 07 14 15 17 19

С: 06

Повторяем данную операцию:

А: 12 18 42 44 55

В: 14 15 17 19

С: 06 07

Эта операция повторяется до тех пор, пока один из исходных файлов не закончится:

А: 42 44 55

В: пустой

С: 06 07 12 14 15 17 18 19

После этого оставшиеся элементы непустого файла переписываются в файл С, который будет иметь окончательный вид:

С: 06 07 12 14 15 17 18 19 42 44 55

Таким образом, мы получили отсортированный файл С. рассмотренная схема называется двухпутевым слиянием. Обобщая эту схему, можно получить р-путевое слияние для упорядоченных последовательностей, размещённых в Р-файлах.

Алгоритм Р-путевого слияния

1. Установить г:=Р.

2. Если г>1, то перейти к следующему пункту, иначе к пункту 5.

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

4. Если последовательность, из которой читался элемент, станет пустой, запомнить этот и уменьшить г на 1. Перейти к пункту 2.

5. Переписать оставшиеся элементы непустой последовательности в выходной файл.

Закончить выполнения алгоритма.

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

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

А: 44 551815 1707

В: 12 42 9406 6714 15 19

Используя алгоритм 2х-путевого слияния, выполним слияние первой серии файла А и первой серии файла В. получим следующее значение файла С:

С: 12 42 44 55 94

Далее выполним слияние вторых серий файлов А и В, запишем полученную последовательность в файл С.

С: 12 42 44 55 9406 18 67

Аналогично работаем с третьими сериями, итак до тех пор, пока один из файлов не окажется пустым (в нашем примере файл В). Оставшуюся серию непустого файла (четвёртую серию файла А) переписываем в выходной файл С. В результате получим файл:

С: 12 42 44 55 9406 18 6714 15 15 17 1907

Мы получили выходной файл, состоящий из упорядоченных последовательностей (серий).

Алгоритм слияния серий двух файлов

1. Прочитать начальные элементы каждого файла. Если один из файлов пустой, перейти к пункту 5.

2. Сравнить два элемента и записать минимальный в выходной файл, а на его место прочитать следующий элемент.

3. Если конец серии не достигнут, перейти к пункту 2.

4. Если достигнут конец серии, переписать элементы другого файла до окончания серии и перейти к пункту 1.

5. Если в другом файле имеются серии (хотя бы одна) переписать элементы этих серий в выходной файл. Закончить выполнения алгоритма.

В отличие от предыдущего алгоритма в рассмотренном необходимо обнаружить конец серии.

Это можно сделать одним из следующих способов:

Ключ прочитанной записи сравнивается с ключом следующей записи. Если значение ключа следующей записи меньше, то серия закончена.

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

Серии в файлах делают фиксированной длины.

Вернёмся к последнему примеру. В результате слияний серий мы получили файл С, состоящий из нескольких серий. Однако, в целом файл ещё не отсортирован.

Как продолжить его сортировку? Необходимо разделить этот файл на два файла, переписывая в них поочерёдно серии. В результате такого разделения мы получим новые файлы А и В, состоящие из серий в среднем в два раза большей длины, чем исходные. Затем вновь выполняем слияние и разделение и так до тех пор, пока не получим выходной файл С, состоящий из одной серии. Естественно, такой файл будет отсортирован.

Алгоритм внешней сортировки

1. Используя оперативную память, сформировать как можно более длинные серии из элементов заданного файла. Распределить эти серии на несколько файлов.

2. Сформировать более длинные серии путём слияния серий нескольких файлов. Вновь распределить эти серии на несколько файлов. Повторять эту операцию.

3. Если в конце образуется одна серия, закончить сортировку.