Методы сортировки и поиска

       

Прямое слияние


Начнем с того, как можно использовать в качестве метода внешней сортировки алгоритм простого слияния, обсуждавшийся в конце предыдущей части. Предположим, что имеется последовательный файл A, состоящий из записей a1, a2, ..., an (снова для простоты предположим, что n представляет собой степень числа 2). Будем считать, что каждая запись состоит ровно из одного элемента, представляющего собой ключ сортировки. Для сортировки используются два вспомогательных файла B и C (размер каждого из них будет n/2).

Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение состояния файла A в файлы B и C, а затем слияние файлов B и C в файл A. (Заметим, что процедура слияния для файлов полностью иллюстрируется рисунком 2.14.) На первом шаге для распределения последовательно читается файл A, и записи a1, a3, ..., a(n-1) пишутся в файл B, а записи a2, a4, ..., an - в файл C (начальное распределение). Начальное слияние производится над парами (a1, a2), (a3, a4), ..., (a(n-1), an), и результат записывается в файл A. На втором шаге снова последовательно читается файл A, и в файл B записываются последовательные пары с нечетными номерами, а в файл C - с четными. При слиянии образуются и пишутся в файл A упорядоченные четверки записей. И так далее. Перед выполнением последнего шага файл A будет содержать две упорядоченные подпоследовательности размером n/2 каждая. При распределении первая из них попадет в файл B, а вторая - в файл C. После слияния файл A будет содержать полностью упорядоченную последовательность записей. В таблице 3.1 показан пример внешней сортировки простым слиянием.

Таблица 3.1. Пример внешней сортировки прямым слиянием

Начальное состояние файла A 8 23 5 65 44 33 1 6
Первый шаг
Распределение


Файл B
Файл C
Слияние: файл A

8 5 44 1 23 65 33 6 8 23 5 65 33 44 1 6
Второй шаг
Распределение
Файл B
Файл C
Слияние: файл A

  8 23 33 44 5 65 1 6 5 8 23 65 1 6 33 44
Третий шаг
Распределение
Файл B
Файл C
Слияние: файл A

  5 8 23 65 1 6 33 44 1 5 6 8 23 33 44 65

Заметим, что для выполнения внешней сортировки методом прямого слияния в основной памяти требуется расположить всего лишь две переменные - для размещения очередных записей из файлов B и C. Файлы A, B и C будут O(log n) раз прочитаны и столько же раз записаны.

Содержание раздела