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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

80
Алгоритм H. (Пирамидальная сортировка.) Записи R
1
, …, R
N
пере-
размещаются на том же месте; после завершения сортировки их ключи
будут упорядочены: K
1
≤ … ≤ K
N
. Сначала файл перестраивается в пира-
миду, после чего вершина пирамиды многократно исключается и записы-
вается на своё окончательное место. Предполагается, что N ≥ 2.
Н1. [Начальная установка.]
12/ +← Nl
, r ← N.
H2. [Уменьшить l или r.] (Если на данный момент l > 1, то происхо-
дит преобразование исходного файла в пирамиду. Если же l = 1, то это
значит, что ключи K
1
, K
2
, …, K
r
уже образуют пирамиду.) Если l > 1, то
l ← l – 1, R ← R
l
, K ← K
l
; в противном случае R ← R
r
, K ← K
r
, R
r
← R
1
,
r ← r – 1. Если в результате оказалось, что r = 1, то R
1
← R и завершить
работу алгоритма.
Н3. [Приготовиться к «протаскиванию».] j ← l. (К этому моменту
2/j
K
≥ K
j
при l <
2/
j
< j ≤ r, (52)
а записи R
k
, r < k ≤ N, занимают свои окончательные места. Шаги Н3…Н8
называются алгоритмом «протаскивания»; их действие эквивалентно
присваиванию R
l
← R с последующим перемещением записей R
l
, …, R
r
таким образом, чтобы условие (52) выполнялось и при l =
2/
k
.)
Н4. [Продвинуться вниз.] i ← j, j ← 2j. (В последующих шагах
i =
2/
j
.) Если j < r, то перейти к шагу Н5; если j = r, то перейти к шагу
Н6; если же j > r, то перейти к шагу Н8.
Н5. [Найти большего сына.] Если K
j
< K
j+1
; то j ← j + 1.
H6. [Больше, чем K?] Если K ≥ K
j
, то перейти к Н8.
Н7. [Поднять его вверх.] Присвоить R
i
← R
j
и вернуться к шагу Н4.
Н8. [Занести R.] Присвоить R
i
← R. (На этом алгоритм «протаскива-
ния», начатый на шаге Н3, заканчивается.) Вернуться к шагу Н2. ■
Упражнения
1. Отсортируйте методом кубического выбора последовательность
из двадцати семи ключей: 48, 7, 22, 10, 51, 69, 5, 62, 26, 16, 60, 78, 97, 14,
66, 9, 8, 83, 96, 20, 56, 41, 98, 63, 28, 66, 9 и установите количество срав-
нений пар ключей, которые будут при этом выполнены.
2. Для традиционной последовательности шестнадцати ключей:
503
87
512
61
908
170
897
275
653
426
154
509
612
677
765
703
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Страницы