Стр. 95 - Основы алгоритмов и структур данных

Содержание 93
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
5.5. Внешняя сортировка
5.5.1. Прямое слияние
Сортировка методом слияния применяется в случае, когда данные из-за
своего размера не помещаются в оперативной памяти и находятся на жёстком
диске. В таком случае мы говорим, что данные представляют собой
“последовательный” файл, т.е. доступна в каждый момент времени только одна
компонента.
Слияние означает объединение двух или более последовательностей в одну
единственную упорядоченную последовательность с помощью повторяющего-
ся выбора из доступных в данный момент элементов.
Одна из сортировок на основе слияния называется сортировка простым
слиянием.
Она выполняется следующим образом:
Пусть у нас есть (2+1) файл (2 рабочих файлов и один исходный файл, где
изначально расположены ключи и куда будет помещена отсортированная
последовательность).
1. Последовательность разбиваем на 2 подпоследовательности.
2. Эти подпоследовательности сливаюся, причём элементы,
расположенные на одном месте в разных файлах, образуют упорядоченные
последовательности длины 2 в исходном файле.
3. Полученная последовательность вновь обрабатывается, как указано в
пунктах 1 и 2. При этом упорядоченные последовательности длинны 2
переходят в упорядоченные последовательности длинны 4.
4. Повторяя предыдущие моменты, мы будем получать упорядоченные
последовательности длинны 8, 16,… и т.д. до тех пор, пока не будет
упорядочена целиком вся последовательность.
Пример
Пусть у нас имеется 2 вспомогательных файла и нам необходимо
упорядочить последовательность:
44, 55, 12, 42, 94, 18, 06, 67.
После разбиения получаем 2- е последовательности:
44* 55* 12* 42*
94* 18* 06* 67*.
Слияние одиночных компонент (т.е. упорядоченных последовательностей
длинны 1) в упорядоченные пары даёт последовательность:
44 94’ 18 55’ 06 12’ 42 67’.
Деля эту последовательность на 2 файла, получаем:
44 94* 18 55*