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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

95
Файл 1 R
1
… R
4 000 000
.
Файл 2 R
4
000
001
… R
5
000
000
.
(54)
Наконец, после еще одного обнуления указателей и слияния данных
в файле 3 окажется отрезок R
1
… R
5 000 000
, и сортировка закончится.
Сбалансированное слияние легко обобщается на случай Т файлов
для любого Т ≥ 3. Выберем произвольное число Р такое, что 1 ≤ Р < Т, и
разделим Т файлов на два «банка»: Р файлов в левом банке и (Т – Р) фай-
лов в правом банке. Распределим исходные отрезки как можно равно-
мернее по Р файлам левого «банка», затем выполним Р-путевое слияние
слево направо, после этого – (Т – Р)-путевое слияние справа налево и т.д.,
пока сортировка не завершится. Обычно значение Р лучше всего выби-
рать равным
2/T
.
Отметим, что частный случай сбалансированного слияния при Т = 4
и Р = 2 соответствует сбалансированному двухпутевому слиянию.
Вновь рассмотрим предыдущий пример, но с использованием боль-
шего количества файлов. Если Т = 6 и Р = 3, то начальное распределение
будет следующим:
Файл 1 R
1
… R
1 000 000
; R
3 000 001
… R
4 000 000
.
Файл 2 R
1 000 001
… R
2 000 000
; R
4 000 001
… R
5 000 000
.
Файл 3 R
2
000
001
… R
3
000
000
.
(55)
Первый проход слияния приведёт к состоянию:
Файл 4 R
1
… R
3 000 000
.
Файл 5 R
3 000 001
… R
5 000 000
.
Файл 6 (пустой)
(56)
При этом предполагается, что в файле 3 помещён фиктивный отре-
зок. По окончании второго прохода слияния сортировка завершается, и
отрезок R
1
… R
5 000 000
помещается в файл 1.
Отметим, что рассмотренный случай для Т = 6 эквивалентен случаю
для Т = 5, так как шестой файл будет задействован при сортировке лишь
для S ≥ 7.
Сбалансированное слияние кажется очень простым и естественным.
Но если приглядеться внимательнее, то видно, что это не наилучший
способ в рассмотренных выше частных случаях. Вместо того чтобы пере-
ходить от (52) к (53) и обнулять указатели всех файлов, следовало
бы остановить первое слияние, когда файлы 3 и 4 содержали соответст-
венно R
1
… R
2 000 000
и R
2 000 001
… R
4 000 000
, а файл 1 был готов к считыва-

Страницы