Таблица 7

КОЛИЧЕСТВО ПЕРЕЗАПИСЕЙ НА ПРОХОД: ЭКСПЕРИМЕНТЫ ПРИ TV = 20000

оказывается не хуже любого другого. Но для больших значений N можно рекомендовать последовательность Седгевика (11), которая обрывается на /t( i, если 3ht > N.

В упр. 43 продемонстрировано, как удалить проверку г > О на шаге D5. Это изменение позволяет ускорить сортировку примерно на 10%.

Вставки в список. Оставим теперь метод Шелла и рассмотрим другие пути усовершенствования метода простых вставок. Среди общих способов улучшения алгоритма один из самых важных основывается на тщательном анализе структур данных, поскольку реорганизация структур данных, позволяющая избежать ненужных операций, часто дает существенный эффект. Дальнейшее обсуждение этой общей идеи можно найти в разделе 2.4, в котором рассматривается довольно сложный алгоритм. Посмотрим, как она применяется к такому нехитрому алгоритму, как простые вставки. Какова наиболее подходящая структура данных для алгоритма S? Сортировка методом простых вставок состоит из двух основных операций:

i) просмотра упорядоченного массива для нахождения наибольшего ключа, меньшего или равного данному ключу;

ii) вставки новой записи в определенное место упорядоченного массива. Массив - это, очевидно, линейный список, и алгоритм S обрабатывает его, используя последовательное распределение (раздел 2.2.2); поэтому для выполнения каждой операции вставки необходимо переместить примерно половину записей. С другой стороны, нам известно, что для вставок идеально подходит хранение данных в памяти в виде связного списка (раздел 2.2.3), так как при этом требуется изменить лишь несколько связей; другая операция - последовательный просмотр - при использовании связного списка почти так же проста, как и при последовательном размещении данных. Поскольку списки всегда просматриваются в одном и том же направлении, достаточно иметь списки с однонаправленной связью. Таким образом, приходим к выводу, что "правильная" структура данных для метода простых вставок - линейные списки с однонаправленными связями. Целесообразно также изменить алгоритм S, чтобы список просматривался в порядке возрастания.

Алгоритм L {Метод вставки в список). Предполагается, что записи Ri,...,Rn содержат ключи Кх,... ,Кы и поля связи Lx,. . ,Ln, в которых могут храниться числа от О до N\ имеется также еще одно поле связи Lo в некоторой искусственной записи Ro в начале массива. Алгоритм устанавливает поля связи так, что записи оказываются связанными в порядке возрастания. Так, если р{\).. .p{N) - "устойчивая" перестановка, такая, что Kpi) < < Крм), то в результате применения алгоритма получим

Lo = р{1); Lpi) = р{г + 1) при 1 < г < ЛГ; Lp(yv) = 0. (13)

Ll. [Цикл по j.] Присвоить Lo N, Ln 0. (Lo служит "головным" элементом списка, а О - пустой связью; следовательно, список, по существу, циклический.) Выполнить шаги от L2 до L5 при j = N - 1, N-2, 1 и завершить процедуру.

L2. [Установка р, q, К.] Присвоить р Lo, q +- О, К Kj. (На последующих шагах запись Rj будет вставлена в нужное место в связном списке путем сравнения ключа К с предыдущими ключами в порядке возрастания. Переменные р ti q служат указателями на текущее место в списке, причем р = Lq, так что q всегда на один шаг отстает от р.)

L3. [Сравнение К : Кр.] Если К < Кр, то перейти к шагу L5. (Найдено искомое положение записи R в списке между Rg и Rp.)

L4. [Продвинуть р, q.] Присвоить q <- р, р <- Lq. Если р > О, то возвратиться к шагу L3. (Если р = О, то К - наибольший ключ, обнаруженный до сих пор; следовательно, запись R должна попасть в конец списка, между Л, и Rq.)

L5. [Вставка в список.] Присвоить L, j, Lj i- p.

Этот алгоритм важен не только потому, что он является простым методом сортировки, но и потому, что он часто входит в состав других алгоритмов обработки списков. В табл. 8 показано несколько первых шагов сортировки шестнадцати чисел, выбранных нами для примеров.

Таблица 8

ПРИМЕР РЕАЛИЗАЦИИ МЕТОДА ВСТАВКИ В СПИСОК

j: О 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Kj-. - 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703 Lj: 16 - -- -- -- -- -- -- -- О

Lj: 16 - -- -- -- -- -- -- - О 15

Lj-: 14 ------------ - 16 О 15

Программа L {Метод вставки в список). Предполагается, что ключ Kj хранится по адресу INPUT+j (0:3), а Lj хранится по адресу INPUT+j(4:5). Значения в регистрах таковы: гП = j; г12 = р; г13 = q; гА(0:3) - К.

01 KEY EQU 0:3

02 LINK EQU 4:5

Ы. Цикл по j. j <- N. Lo <- N. Ln <r- 0.

Переход на уменьшение j. L2. Установка p, q, К. p <- Lo. 5 <- 0. К <r-Kj. A L3. Сравнить К : K. A Перейти к шагу L5, если К < Кр. L4. Продвинуть р, д. q <- р. p<r-Lg.

Перейти к шагу L3, если р > 0. L5. Вставить в список. <- j. Lj <- p.

N>j>l. I

Время выполнения этой программы равно 7В + 14N -ЗА -6 машинных циклов, где N - длина массива, А+1 - число правосторонних максимумов, а В - число инверсий в исходной перестановке. (Ср. с анализом программы S. Обратите внимание, что программа L не перемещает записи в памяти; это можно сделать, как в упр. 5.2-12, затратив дополнительно 207V машинных циклов.) Программа S требует (9В-1-107V -ЗЛ - 9)ы, а так как В равно примерно jN, то нетрудно видеть, что за счет дополнительного пространства памяти, выделенного для полей связи, удалось сэкономить примерно 22% времени выполнения. Тщательно продумав программу, можно сберечь еще 22% (см. упр. 33), но время выполнения все же останется пропорциональным N.

Подведем итог сделанному. Мы начали с алгоритма S - простого и очевидного алгоритма сортировки, который выполняет около jTV сравнений и около 7V перемещений записей данных в памяти. Этот алгоритм был усовершенствован путем использования бинарных вставок, при которых выполняется около NlgN сравнений и 7V перемещений записей данных в памяти. Несколько изменив структуру данных, применив двухпутевые вставки, нам удалось сократить число перезаписей до №. При сортировке методом Шелла с убывающим смещением число сравнений и перезаписей снижается примерно до N/ для тех значений N, которые встречаются на практике; при N со это число можно сократить до порядка 7V(log7V). Дальнейшее стремление улучшить алгоритм S с помощью связной структуры данных привело нас к методу вставки в список, который требует около 7V сравнений, О перезаписей и 2 операций изменения связи.

Можно ли объединить лучшие свойства этих методов, т. е. сократить число сравнений до порядка NlogN, как при бинарных вставках, и в то же время исключить перемещения записей в памяти, как при вставках в список? Ответ утвердительный - нужно перейти к древовидной структуре данных. Такой вариант впервые был исследован в 1957 году Д. Дж. Уилером (D. J. Wheeler), который предложил использовать двухпутевые вставки до тех пор, пока не возникнет необходимость перемещать записи в памяти. Вместо операции перезаписи он предложил вставлять указатель на новую область памяти и рекурсивно применять ту же процедуру ко всем элементам, которые должны вставляться в эту новую область памяти. Ориги-