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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

96
нию R
4 000 001
… R
5 000 000
. Затем указатели файлов 2, 3, 4 могли быть обну-
лены, и сортировка завершилась бы трёхпутевым слиянием в файл 2.
Общее число записей, прочитанных из файлов в ходе этой процедуры, со-
ставило бы 4 000 000 + 5 000 000 = 9 000 000 против 5 000 000 + 5 000 000 +
+ 5 000 000 = 15 000 000 в сбалансированной схеме.
Имея пять отрезков и четыре файла, можно поступить ещё лучше,
распределив отрезки следующим образом:
Файл 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
.
Файл 4 (пустой)
(57)
Теперь, выполнив трёхпутевое слияние в файл 4, затем обнуление
указателей файлов 3 и 4 с последующим трёхпутевым слиянием в файл 3,
можно было бы завершить сортировку, прочитав всего 3 000 000 +
+ 5 000 000 = 8 000 000 записей.
Наконец, если бы имелось шесть файлов, то можно было бы запи-
сать исходные отрезки в файлы 1 – 5 и закончить сортировку за один
проход, выполнив пятипутевое слияние в файл 6. Рассмотрение этих слу-
чаев показывает, что простое сбалансированное слияние не является наи-
лучшим, и поэтому имеет смысл поиск улучшенных схем слияния.
Далее внешнюю сортировку в следующем параграфе исследуем бо-
лее глубоко. Рассмотрим фазу внутренней сортировки, порождающей
начальные отрезки. Здесь особый интерес представляет технология «вы-
бора с замещением», которая порождает длинные отрезки, значительно
превосходящие ёмкость внутренней памяти. Обсудим структуры данных,
удобные для целей многопутевого слияния, а также важнейшие схемы
слияния.
Упражнения
1. В данном параграфе внешней сортировке предшествует фаза
внутренней сортировки. Установите, можно ли не выполняя внутренней
сортировки, производить слияние записей во все более и более длинные
отрезки с самого начала.
2. Установите, каким будет содержимое файлов (аналогичное (52) –
(54)), если записи R
1
… R
5 000 000
сортируются с помощью трёхфайлового
сбалансированного метода при Р = 2. Сравните этот случай со слиянием
на четырёх файлах. Оцените, сколько проходов по всем данным будет
сделано после первоначального распределения отрезков.

Страницы