Методы программирования. Громов Ю.Ю - 94 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

94
Рассмотрим процесс внешней сортировки, использующий сбаланси-
рованное двухпутевое слияние, в основе которого лежит идея, применён-
ная ранее в алгоритмах N, S и L (см. параграф 14). В процессе слияния
нам потребуются четыре рабочих файла.
На протяжении первой фазы возрастающие отрезки, получаемые
при внутренней сортировке, помещаются поочередно в файлы 1 и 2 до
тех пор, пока не исчерпаются исходные данные. Затем указатели файлов
1 и 2 обнуляются и сливаются отрезки, находящиеся в этих файлах, и
получаются новые отрезки, вдвое длиннее исходных. Эти новые отрезки
записываются по мере их формирования попеременно в файлы 3 и 4.
(Если в файле 1 на один отрезок больше, чем в файле 2, то предполагает-
ся, что файл 2 содержит дополнительный «фиктивный» отрезок длины 0.)
Затем файловые указатели всех файлов обнуляются, и содержимое фай-
лов 3 и 4 сливается в удвоенные по длине отрезки, записываемые пооче-
редно в файлы 1 и 2. Процесс продолжается (при этом длина отрезков
каждый раз удваивается) до тех пор, пока не останется один отрезок
(а именно весь упорядоченный файл). Если после внутренней сортировки
было получено S отрезков, причём 2
k–1
< S ≤ 2
k
, то процедура сбалансиро-
ванного двухпутевого слияния произведёт ровно
Sk
2
log=
проходов
по всем данным.
Например, в рассмотренной выше ситуации, когда требуется упоря-
дочить 5 000 000 записей, а объём внутренней памяти составляет 1 000 000
записей, мы имеем S = 5 и k = 3. Начальная распределительная фаза про-
цесса сортировки поместит пять отрезков в файлы следующим образом:
Файл 1 R
1
… R
1 000 000
; R
2 000 001
… R
3 000 000
; R
4 000 001
… R
5 000 000
.
Файл 2 R
1 000 001
… R
2 000 000
; R
3 000 001
… R
4 000 000
.
Файл 3 (пустой)
Файл 4 (пустой)
(52)
Поскольку записей в файле 2 оказалось меньше, чем в файле 1, в ко-
нец файла 2 неявно добавляется фиктивный отрезок.
После первого прохода слияния в файлах 3 и 4 получатся в два раза
более длинные отрезки, чем в файлах 1 и 2:
Файл 3 R
1
… R
2 000 000
; R
4 000 001
… R
5 000 000
.
Файл 4 R
2
000
001
… R
4
000
000
.
(53)
Заметим, что за счёт фиктивного отрезка в файле 2 отрезок R
4 000 001
… R
5 000 000
просто был скопирован из файла 1 в файл 3. После обнуления
указателей всех четырёх файлов будет выполнен второй проход по дан-
ным и их слияние, что приведёт к такому результату:

Страницы