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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

136
Содержимое стопок после третьего просмотра
§ 16
1. Без предварительной фазы внутренней сортировки обойтись
можно, но при этом сортировка значительно замедлится, поскольку воз-
растёт число считываний каждой части данных из внешней памяти и за-
писи в неё.
2. Первоначальное распределение отрезков по файлам будет таким:
Файл 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 (пустой)
Затем будет выполнено двухпутевое слияние из первого и второго
файлов в третий файл:
Файл 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 R
1
… R
2
000
000
; R
2
000
001
… R
4
000
000
; R
4
000
001
… R
5
000
000
.
После обнуления указателей всех файлов и «однопутевого» слияния
(распределения) из файла 3 в файлы 1 и 2 будет получено следующее
состояние файлов:
Файл 1 R
1
… R
2 000 000
; R
4 000 001
… R
5 000 000
.
Файл 2 R
2 000 001
… R
4 000 000
.
Файл 3 R
1
… R
2
000
000
; R
2
000
001
… R
4
000
000
; R
4
000
001
… R
5
000
000
.
Затем файлы 1 и 2 сливаются в файл 3:
Файл 1 R
1
… R
2 000 000
; R
4 000 001
… R
5 000 000
.
Файл 2 R
2 000 001
… R
4 000 000
.
Файл 3 R
1
… R
4
000
000
; R
4
000
001
… R
5
000
000
.
047
TOP[4]
TOP[5]
TOP[6]
TOP[7]
TOP[8]
TOP[9]
TOP[0]
TOP[1]
TOP[2]
TOP[3]
BOTM[9]
BOTM[8]
BOTM[7]
BOTM[6]
BOTM[5]
BOTM[4]
BOTM[3]
BOTM[2]
BOTM[1]
BOTM[0]
905
012
858
841
874
701
623
610
589
555
379
322
390
167

Страницы