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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

65
тельно хорошо упорядоченные файлы. Поэтому здесь можно пользовать-
ся простыми вставками и записи будут довольно быстро достигать своего
конечного положения.
Последовательность шагов 8, 4, 2, 1 не следует считать незыблимой,
а можно пользоваться любой последовательностью h
t
, h
t–1
, …, h
1
, в кото-
рой последний шаг h
1
равен 1. Например, те же шестнадцать записей
можно отсортировать с шагами 7, 5, 3, 1. Отметим, что из всех возмож-
ных последовательностей шагов одни последовательности могут оказать-
ся гораздо лучше других.
Алгоритм D. (Сортировка с убывающим шагом.)
Записи R
1
, R
2
, …, R
N
переразмещаются на том же месте памяти. По-
сле завершения сортировки их ключи будут упорядочены: K
1
≤ … ≤ K
N
.
Для управления процессом сортировки используется вспомогательная
последовательность шагов h
t
, h
t–1
, …, h
1
, где h
1
= 1. Выбрав правильную
последовательность шагов, можно значительно сократить время сорти-
ровки. При t = 1 этот алгоритм сводится к алгоритму S.
D1. [Цикл по s.] Выполнить шаг D2 при s = t, t – 1, …, 1 и закончить
алгоритм.
D2. [Цикл по j.] Реализовать присваивание h ← h
s
и шаги D3…D6
при j = h + 1, h + 2, …, N. (Для сортировки элементов, отстоящих друг от
друга на h позиций, воспользуемся простыми вставками и в результате
получим K
i
≤ K
i+h
при 1 ≤ i ≤ N – h. Шаги D3…D6, по существу, такие же,
как соответственно шаги S2…S5 в алгоритме S.)
D3. [Установка i, K, R.] Присвоить i ← j – h, K ← K
j
, R ← R
j
.
D4. [Сравнение K с K
i
.] Если K ≥ K
i
, то перейти к шагу D6.
D5. [Перемещение R
i
.] Выполнить присваивания R
i+h
← R
i
, i ← i – h.
Если после этого будет i > 0, то вернуться к шагу D4.
D6. [Запись R на место R
i+h
.] Присвоить R
i+h
← R. ■
Эксперименты по оценке времени работы алгоритма D показали, что
для диапазона 100 ≤ N ≤ 250 000 «наиболее подходящими» формулами
оценки являются 1.21 N
1.26
и 0.39N (ln N)
2
– 2.33N ln N. Последователь-
ность же шагов h
t
, h
t–1
, …, h
1
разумно выбирать по правилу:
h
1
← 1, h
s + 1
← 3h
s
+ 1 и остановиться на h
t
, когда h
t + 2
≥ N. (47)
Это правило, например для N = 100, даёт последовательность шагов
13, 4, 1.
Оставим метод Шелла и рассмотрим другие пути усовершенствова-
ния метода простых вставок. Одним из самых важных среди общих спо-
собов улучшения алгоритма сортировки является способ, который осно-
вывается на тщательном анализе структур данных и называется вставка-
ми в список.

Страницы