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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

66
Заметим, что последовательность записей является линейным спи-
ском и алгоритм S обрабатывает его, используя последовательное рас-
пределение памяти. Именно поэтому для выполнения каждой операции
вставки необходимо переместить примерно половину записей. Но, как
известно, для вставок идеально подходит связанное распределение памя-
ти, так как при этом требуется изменить всего лишь несколько связей.
Поскольку последовательности записей при сортировке простыми вста-
вами просматриваются всегда в одном и том же направлении, то их дос-
таточно представлять односвязными списками.
Приведём алгоритм, предполагающий, что записи R
1
, R
2
, …, R
N
со-
держат ключи K
1
, K
2
, …, K
N
и поля связи L
1
, L
2
, …, L
N
, в которых могут
храниться числа от 0 до N. Кроме того, имеется ещё одно поле связи L
0
в
некоторой искусственной записи R
0
в начале списка. Алгоритм устанав-
ливает поля связи так, что записи оказываются связанными в возрастаю-
щем порядке. Так, если p(1) … p(N) является устойчивой перестановкой
такой, что K
p(1)
≤ … ≤ K
p(N)
, то в результате применения алгоритма полу-
чим L
0
= p(1); L
p(i)
= p(i + 1) при i = 1, 2, …, N – 1; L
p(N)
= 0.
Алгоритм L. (Вставки в список.)
L1. [Цикл по j.] Присвоить L
0
← N, L
N
← 0. (Поскольку L
0
является
«головой» списка, 0 – пустой связью, то список, по существу, цикличе-
ский.) Выполнить шаги L2…L5 для j = N – 1, N – 2, …, 1 и завершить ра-
боту алгоритма.
L2. [Установка p, q, K.] Выполнить p ← L
0
, q ← 0, K ← K
j
. (В по-
следующих шагах запись R
j
встанет в нужное место в связанном списке
путём сравнения ключа K с предыдущими ключами в возрастающем по-
рядке. Переменные p и q служат указателями на текущее место в списке,
причём p = L
q
, т.е. q всегда на один шаг отстаёт от p.)
L3. [Сравнение K и K
p
]. Если K ≤ K
p
, то перейти к шагу L5. (Найдено
искомое положение записи R в списке между записями R
q
и R
p
.)
L4. [Продвижение p и q]. Присвоить q ← p, p ← L
q
. Если p > 0, то
вернуться к шагу L3. (Если p = 0, то K – наибольший ключ, обнаружен-
ный до сих пор. Следовательно, запись R должна попасть в конец списка,
между записями R
q
и R
0
.)
L5. [Вставка в список]. Выполнить L
q
← j, L
j
← p. ■
Заметим, что этот алгоритм важен не только как простой метод сор-
тировки, но и потому, что он часто используется в других алгоритмах
обработки списков. Время его выполнения равно (7B + 14N – 3A – 6) u,
где N – число записей, А – число правосторонних максимумов, B – число
инверсий в исходной перестановке. По сравнению с алгоритмом S, здесь
удаётся сэкономить примерно 22% времени работы, но оно по-прежнему
остаётся в среднем пропорциональным N
2
.

Страницы