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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

73
Q4. [Запись R на место R
i
.] (К этому моменту K
i
– ключ, не меньший
чем K и находящийся не на своём месте, кроме того K ≥ K
j
.) Если j ≤ i, то
R
i
← R и перейти к шагу Q7; в противном случае R
i
← R
j
и увеличить i на 1.
Q5. [Сравнение K
i
и K.] Если K
i
< K, то i увеличить на 1 и повторить
этот шаг.
Q6. [Запись R на место R
j
.] (К этому моменту K
j
– ключ, не больший
чем K и находящийся не на своём месте, кроме того K ≤ K
i
.) Если j ≤ i, то
R
j
← R и i ← j; в противном случае R
j
← R
i
, значение j уменьшить на 1 и
вернуться к шагу Q3.
Q7. [Включение в стек.] (Теперь подфайл R
l
, …, R
i
, …, R
r
разделён
так, что K
k
≤ K
i
при l ≤ k ≤ i и K
i
≤ K
k
при i ≤ k ≤ r.) Если r – i ≥ i – l, то па-
ру (i + 1, r) включить в стек и r ← i – 1; в противном случае пару (l, i – 1)
включить в стек и l ← i + 1. (Каждый элемент стека вида (a, b) является
заявкой на сортировку подфайла R
a
, …, R
b
в одной из последующих ста-
дий.) Вернуться к шагу Q2.
Q8. [Сортировка простыми вставками.] Для j = l + 1, l + 2, …, r вы-
полнять следующие операции: сначала K ← K
j
, R ← R
j
, i ← j – 1; затем
R
i+1
← R
i
и i ← i – 1 нуль или более раз, пока выполняется условие K
i
> K;
наконец R
i+1
← R. (Это, по существу, алгоритм S, применённый к подфай-
лу из M или менее элементов.)
Q9. [Исключение из стека.] Если стек пуст, то конец алгоритма; в
противном случае взять верхний элемент стека (l’, r’), присвоить l ← l’,
r ← r’ и вернуться к шагу Q2. ■
Отметим, что «наилучшее» значение М (для гипотетической машины
MIX) равно девяти. Если M = 9, то при больших значениях N среднее время
работы алгоритма примерно равно (12.67(N + 1) ln N – 1.92 N – 14.59) u.
Следовательно, алгоритм Q работает в среднем довольно быстро,
кроме того, он требует очень мало памяти. Но следует отметить, что наи-
худшим случаем для алгоритма Q является тот, когда исходный файл уже
упорядочен. При этом каждая операция «разделения» становится почти
бесполезной, поскольку каждый выделяемый подфайл состоит из одного
элемента. И самый, казалось бы, простой для сортировки файл будет сор-
тироваться по алгоритму Q с затратами времени, пропорциональными N
2
.
Таким образом, в отличие от рассмотренных ранее алгоритмов сор-
тировки, алгоритм Q предпочитает неупорядоченные файлы.
Упражнения
1. Методом пузырька по алгоритму B отсортируйте последователь-
ность из тринадцати записей: (47 «придерживай»), (79 «за»), (94 «козырёк»),
(41 «высокие»), (30 «людей»), (10 «на»), (12 «высоких»), (77 «свой»),
(36 «и»), (96 «.»), (7 «Взирая»), (44 «предметы»), (69 «картуз»).

Страницы