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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

63
11. СОРТИРОВКА ВСТАВКАМИ
Сортировка вставками заключается в следующем: предполагается,
что перед рассмотрением записи R
j
предыдущие записи R
1
, R
2
, …, R
j–1
уже упорядочены, и запись R
j
вставляется в подходящее место. На основе
этой схемы возможны несколько любопытных вариаций.
Сортировка простыми вставками относится к наиболее очевидным
сортировочным процедурам. Пусть 1 < j ≤ N, а записи R
1
, R
2
, …, R
j–1
уже
размещены так, что K
1
≤ K
2
≤ … ≤ K
j–1
. Будем сравнивать ключ K
j
по оче-
реди с ключами K
j–1
, K
j–2
, … до тех пор, пока не обнаружим, что запись
R
j
следует вставить между записями R
i
и R
i+1
. Тогда передвинем записи
R
i+1
, …, R
j–1
на одно место вверх и поместим новую запись в позицию i + 1.
В представленном ниже алгоритме записи R
1
, R
2
, …, R
N
переразме-
щаются на том же месте памяти. После завершения сортировки их ключи
будут упорядочены: K
1
≤ … ≤ K
N
.
Алгоритм S. (Сортировка простыми вставками.)
S1. [Цикл по j.] Выполнить шаги S2…S5 для j = 2, 3, …, N и завер-
шить алгоритм.
S2. [Установка i, K, R.] Выполнить присваивания: i ← j – 1, K ← K
j
,
R ← R
j
. (В последующих шагах делается попытка вставить запись R в
нужное место, сравнивая ключ K с ключами K
i
при убывающих значени-
ях i.)
S3. [Сравнение K с K
i
.] Если K ≥ K
i
, то перейти к шагу S5. (Найдено
искомое место для записи R.)
S4. [Перемещение R
i
, уменьшение i.] Выполнить: R
i+1
← R
i
, i ← i – 1.
Если i > 0, то вернуться к шагу S3. (Если i = 0, то K – наименьший ключ
из рассмотренных до сих пор ключей, а, значит, запись R должна занять
первую позицию.)
S5. [Запись R на место R
i+1
.] Выполнить присваивание R
i+1
← R. ■
Заметим, что время работы алгоритма равно (9B + 10N – 3A – 9) u,
где N – число сортируемых записей; A – число случаев, когда на шаге S4
значение i убывает до нуля; B – число перемещений. Среднее время рабо-
ты алгоритма S в предположении, что все ключи различны и расположе-
ны в случайном порядке, равно (2.25N
2
+ 7.75N – 3H
N
– 6) u.
Обсудим так называемые бинарные вставки. Когда при сортировке
простыми вставками обрабатывается j-я запись, её ключ сравнивается в
среднем с j
/
2 ранее отсортированными ключами. Поэтому общее число
сравнений равно приблизительно N
2
/4, а это очень много, даже если N
умеренно велико.
Метод бинарного поиска позволяет определить место, куда встав-
лять j-й элемент после приблизительно log
2
j соответствующим образом
выбранных сравнений. Например, если вставляется 64-я запись, можно
сначала сравнить ключ K
64
с K
32
; затем, если он меньше, сравнить его с

Страницы