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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

84
N11. [Ступенька вниз?] Увеличить i на 1. Затем, если K
i–1
≤ K
i
, то
вернуться к шагу N10.
N12. [Переключение направления.] Присвоить f ← 0, d ← – d и
взаимозаменить k ↔ l. Вернуться к шагу N3.
N13. [Переключение областей.] Если f = 0, то присвоить s ← 1 – s и
вернуться к шагу N2. В противном случае сортировка завершена; если
s = 0, то присвоить (R
1
, …, R
N
) ← (R
N+1
, …, R
2N
). (Если результат можно
оставить в области (R
N+1
, …, R
2N
), то выполнение последнего копирования
необязательно.) ■
Проанализируем данный алгоритм. Если файл случаен, то в нём
имеется около
2
1
N возрастающих отрезков, так как K
i
> K
i+1
с вероятно-
стью
2
1
. При каждом просмотре число отрезков сокращается вдвое, за
исключением необычных случаев. Таким образом, число просмотров, как
правило, составляет около log
2
N. При каждом просмотре должны быть
переписаны все N записей, и большая часть времени затрачивается в ша-
гах N3, N4, N5, N8 и N9. Если считать, что равные ключи встречаются с
малой вероятностью, то при каждом просмотре на каждую запись затра-
чивается 12.5 единиц времени, и общее время работы асимптотически
приближается к 12.5N log
2
N как в среднем, так и в наихудшем случае.
Это медленнее быстрой сортировки и не настолько лучше времени рабо-
ты пирамидальной сортировки (16N log
2
N), чтобы оправдать вдвое боль-
ший расход памяти.
В алгоритме N границы между отрезками полностью определяются
«ступеньками вниз». Такой подход обладает тем возможным преимуще-
ством, что исходные файлы с преобладанием возрастающего или убы-
вающего расположения элементов могут обрабатываться очень быстро,
но при этом замедляется основной цикл вычислений. Вместо проверок
ступенек вниз можно принудительно установить длину отрезков, считая,
что все отрезки исходного файла имеют длину 1, после первого просмот-
ра все отрезки (кроме, возможно, последнего) имеют длину 2, …, после
k-го просмотра все отрезки (кроме, возможно, последнего) имеют длину 2
k
.
В отличие от «естественного» слияния в алгоритме N такой способ назы-
вается простым двухпутевым слиянием.
Алгоритм простого двухпутевого слияния очень напоминает алго-
ритм N, тем не менее, методы достаточно отличаются друг от друга.
Алгоритм S. (Сортировка простым двухпутевым слиянием.)
Как и в алгоритме N, при сортировке записей R
1
, …, R
N
используют-
ся две области памяти.
S1. [Начальная установка.] Присвоить s ← 0, р ← 1. (Смысл пере-
менных s, i, j, k, l и d приведён в описании алгоритма N. Здесь р – размер

Страницы