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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

64
ключом K
16
, если больше – с ключом K
48
и т.д. В результате место для
записи R
64
будет найдено после всего лишь шести сравнений. Общее чис-
ло сравнений для N вставляемых элементов равно приблизительно
N log
2
N, что существенно лучше, чем N
2
/4.
К сожалению, бинарные вставки решают задачу только наполовину:
после того, как найдено место для записи R
j
, всё равно нужно перемес-
тить примерно j /
2 ранее отсортированных записей, чтобы освободить
место под запись R
j
. Поэтому общее время работы алгоритма остаётся, по
существу, пропорциональным N
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
Сначала разделим эти записи на восемь групп по две записи в каж-
дой группе: (R
1
, R
9
), (R
2
, R
10
), …, (R
8
, R
16
). В результате сортировки каж-
дой из восьми групп записей в отдельности (8-сортировки) получим по-
следовательность записей со следующим распределением ключей:
503
87
154
61
612
170
765
275
653
426
512
509
908
677
897
703
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Затем разделим все записи на четыре группы по четыре записи в ка-
ждой: (R
1
, R
5
, R
9
, R
13
), …, (R
4
, R
8
, R
12
, R
16
), опять отсортируем каждую
группу в отдельности (4-сортировка) и получим:
503
87
154
61
612
170
512
275
653
426
765
509
908
677
897
703
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Далее выполняется 2-сортировка, в которой сортируются две груп-
пы (R
1
, R
3
, …, R
15
), (R
2
, R
4
, …, R
16
) по восемь записей в каждой группе.
Она даст следующую последовательность ключей:
154
61
503
87
512
170
612
275
653
426
765
509
897
677
908
703
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Процесс завершается 1-сортировкой, в которой сортируются все
шестнадцать записей и в результате получается последовательность:
61
87
154
170
275
426
503
509
512
612
653
677
703
765
897
908
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Заметим, что в каждом из описанных промежуточных процессов
сортировки участвуют либо сравнительно короткие файлы, либо сравни-

Страницы