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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

83
ложнениям. Этот метод по традиции называется естественным слияни-
ем, так как он использует отрезки, которые естественно образуются в
исходном файле.
Таблица 1
503
87 512
61 908
170
897
275
653
426
154
509
612
677
765
703
503
703
765
61 612
908
154
275
426
653
897
509
170
677
512
87
87 503
512
677
703
765
154
275
426
653
908
897
612
509
170
61
61 87 170
503
509
512
612
677
703
765
897
908
653
426
275
154
61 87 154
170
275
426
503
509
512
612
653
677
703
765
897
908
Алгоритм N. (Сортировка естественным двухпутевым слиянием.)
При сортировке записей R
1
, …, R
N
используются две области памяти, ка-
ждая из которых может содержать N записей. Для удобства обозначим
записи, находящиеся во второй области, через R
N+1
, …, R
2N
, хотя в дейст-
вительности запись R
N+1
может и не примыкать непосредственно к R
N
.
Начальное содержимое записей R
N+1
, …, R
2N
не имеет значения. После
завершения сортировки ключи будут упорядочены: K
1
≤ … ≤ K
N
.
N1. [Начальная установка.] Установить s ← 0. (При s = 0 записи из
области (R
1
, …, R
N
) пересылаются в область (R
N+1
, …, R
2N
); при s = 1 об-
ласти по отношению к пересылкам поменяются ролями.)
N2. [Подготовка к просмотру.] Если s = 0, то присвоить i ← 1, j ← N,
k ← N + 1, l ← 2N. Если s = l, то присвоить i ← N + 1, j ← 2N, k ← 1,
l ← N. (Переменные i, j, k, l указывают текущие позиции во входных фай-
лах, откуда идёт чтение, и в выходных файлах, куда идёт запись.) При-
своить d ← 1, f ← 1. (Переменная d определяет текущее направление выво-
да, f устанавливается равной 0, если необходимы дальнейшие просмотры.)
N3. [Сравнение K
i
и K
j
.] Если K
i
> K
j
, то перейти к шагу N8. Если
i = j, то присвоить R
k
← R
i
и перейти к шагу N13.
N4. [Пересылка R
i
.] (Шаги N4…N7 аналогичны шагам М3…М4
алгоритма М.) Установить R
k
← R
i
, k ← k + d.
N5. [Ступенька вниз?] Увеличить i на 1. Затем, если K
i–1
≤ K
i
, то вер-
нуться к шагу N3.
N6. [Пересылка R
j
.] Присвоить R
k
← R
j
, k ← k + d.
N7. [Ступенька вниз?] Уменьшить j на 1. Затем, если K
j+1
≤ K
j
, то
вернуться к шагу N6; в противном случае перейти к шагу N12.
N8. [Пересылка R
j
.] (Шаги N8…N11 двойственны по отношению к
шагам N4…N7.) Установить R
k
← R
j
, k ← k + d.
N9. [Ступенька вниз?] Уменьшить j на 1. Затем, если K
j+1
≤ K
j
, то
вернуться к шагу N3.
N10. [Пересылка R
i
.] Присвоить R
k
← R
i
, k ← k + d.

Страницы