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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

85
возрастающих отрезков, которые будут сливаться во время текущего
просмотра; q и r – количества неслитых элементов в отрезках.)
S2. [Подготовка к просмотру.] Если s = 0, то присвоить i ← 1, j ← N,
k ← N, l ← 2N + 1; если s = 1, то присвоить i ← N + 1, j ← 2N, k ← 0,
l ← N + 1. Затем присвоить d ← 1, q ← p, r ← p.
S3. [Сравнение K
i
и K
j
.] Если K
i
> K
j
, то перейти к шагу S8.
S4. [Пересылка R
i
.] Присвоить k ← k + d, R
k
← R
i
.
S5. [Конец отрезка?] Присвоить i ← i + 1, q ← q – 1. Если q > 0, то
вернуться к шагу S3.
S6. [Пересылка R
j
.] Присвоить k ← k + d. Затем, если k = l, то перей-
ти к шагу S13; в противном случае присвоить R
k
← R
j
.
S7. [Конец отрезка?] Присвоить j ← j – 1, r ← r – 1. Если r > 0, то
вернуться к шагу S6; в противном случае перейти к шагу S12.
S8. [Пересылка R
j
.] Присвоить k ← k + d, R
k
← R
j
.
S9. [Конец отрезка?] Установить j ← j – 1, r ← r – 1. Если r > 0, то
вернуться к шагу S3.
S10. [Пересылка R
i
.] Установить k ← k + d. Затем, если k = l, то пе-
рейти к шагу S13; в противном случае присвоить R
k
← R
i
.
S11. [Конец отрезка?] Выполнить присваивания i ← i + 1, q ← q – 1.
Если q > 0, то вернуться к шагу S10.
S12. [Переключение направления.] Присвоить q ← p, r ← p, d ← – d
и взаимозаменить k ↔ l. Если j – i < p, то вернуться к шагу S10; в против-
ном случае вернуться к шагу S3.
S13. [Переключение областей.] Установить p ← p + p. Если p < N, то
присвоить s ← 1 – s и вернуться к шагу S2. В противном случае сорти-
ровка завершена. Если s = 0, то присвоить (R
1
, …, R
N
) ← (R
N+1
, …, R
2N
).
(Независимо от распределения записей в исходном файле, последнее ко-
пирование будет выполнено тогда и только тогда, когда значение
N
2
log
нечётно. Таким образом, можно заранее предсказать положение
отсортированного файла, и тогда копирование не потребуется.) ■
Пример работы алгоритма сортировки простым двухпутевым слия-
нием представлен в табл. 2. Отметим, что метод справедлив и тогда, ко-
гда число сортируемых записей N не является степенью двойки. В отли-
чие от алгоритма N, здесь вместо проверок ступенек вниз уменьшаются
значения переменных q и r до достижения равенства нулю. Благодаря
этому время работы алгоритма S асимптотически приближается к
11N log
2
N единицам, что несколько лучше, чем в алгоритме N.
Заметим, что на практике имеет смысл комбинировать алгоритм S с
простыми вставками. Например, вместо первых четырёх просмотров ал-
горитма S можно простыми вставками отсортировать группы из 16 эле-
ментов, исключив довольно расточительные вспомогательные операции,
связанные со слиянием коротких файлов.

Страницы