hg » p*, может иметь время сортировки, которое гарантированно равно 0(7V+) при произвольных малых б > 0.

Рассмотрим, каким на практике может быть значение Л, для чего проанализируем общее время выполнения программы D, а именно - {9В + 10NT + 13Т - 105 - ЗА + 1)и. В табл. о показано среднее время выполнения сортировки для различных последовательностей смещений при N - 8. Заметим, что при таком малом значении N в общем времени выполнения преобладают вспомогательные операции, поэтому наилучшие результаты получаются при t = 1; следовательно, при N = 8 лучше всего пользоваться методом простых вставок. (Среднее время выполнения программы S при 7V = 8 равно всего 191.85ы.) Любопытно, что наилучший результат в двухпроходном алгоритме достигается при hi = 6, поскольку большая величина S оказывается важнее малой величины В. Аналогично три смещения, 3 2 1, минимизируют среднее число перезаписей, но это не самый лучший набор значений для трехпроходной сортировки. Быть может, интересно привести некоторые "наихудшие" перестановки, максимизирующие число перезаписей, так как общий способ построения таких перестановок до сих пор не известен:

/12=5, hi=3, ho = l: 85263741 (19 перезаписей) h2=3, hi =2, ho = l: 835 72461 (17 перезаписей)

С ростом TV наблюдается несколько иная картина. В табл. 6 показаны приближенные значения числа перемещений для различных последовательностей смешений при N = 1000. Первые несколько последовательностей удовлетворяют условию делимости (5), так что можно воспользоваться формулой (6) и упр. 19; для получения средних значений при других последовательностях смещений применялись эмпирические тесты. Были сгенерированы пять тысяч массивов по 1 ООО случайных элементов, и каждый массив сортировался с каждой последовательностью смещений. Стандартное отклонение числа минимумов слева направо обычно составляло около 15, а стандартное отклонение числа перезаписей В обычно составляло около 300.

Эти данные позволяют выявить некоторые характеристики, но поведение алгоритма D все еще остается неясным. Шелл первоначально предполагал использовать смещения [7V/2J, [N/4\, [N/8\, ..., но это нежелательно, если двоичное представле-

Таблица 6

ДАННЫЕ О ВЫПОЛНЕНИИ АЛГОРИТМА D ПРИ = 1000

377 233 144 233 144

ние числа N содержит длинные цепочки нулей. Лазарус и Фрэнк [Lazarus и Frank, САСМ 3 (1960), 20-22] предложили использовать, по существу, ту же последовательность, но добавляя 1 там, где это необходимо, чтобы сделать все смещения нечетными. Хиббард [Hibbard, САСМ 6 (1963), 206-213] предложил использовать смещения вида 2* - 1; Папернов и Стасевич предложили последовательность 2* + 1. Среди других естественных последовательностей, использованных для получения

табл. 6, - последовательности (2* - (-1)*)/3 и (3* - 1)/2, числа Фибоначчи и предложенная Инсерпи и Седгевиком последовательность (8) для р = 2.5 и р = 2. Также включены последовательности {б*"!!} и {713}, аналогичные предложенной Праттом, поскольку они сохраняют асимптотический характер сходимости к 0{N(logN)), но приводят к более низким накладным расходам при малых N. Последний вариант в табл. 6 исходит из другой последовательности, предложенной все тем же Седгевиком, но основанной на несколько измененной эвристике [см. J. Algorithms 7 (1986), 159-173]:

, / 9-2«-9-2*/2 + 1, если S четно; l8-2*-6-2(+i)/2 + l, если S нечетно.

Седгевик доказал, что, когда используются сформированные по этому правилу смещения {Но, /ti, /«2,...) = (1,5,19,41,109,209,...), время выполнения в худшем случае не превышает 0{N*/).

Минимальное число перемещений, 6 600, наблюдается для смещений вида 2* -Ь1, а также в последовательностях Инсерпи и Седгевика при р = 2. Но важно понимать, что надо учитывать не только число перезаписей, хотя именно оно асимптотически доминирует в общем времени работы. Так как время выполнения программы D равно 9В + IOTVTh----единиц (машинных циклов), ясно, что экономия одного прохода примерно эквивалентна сокращению числа перезаписей на N; при N = 1000 целесообразнее добавить 1111 перезаписей, если за счет этого удастся сэкономить один проход. Поэтому представляется неразумным начинать с ht-i, большего, чем, скажем, 7V, поскольку большое значение смещения не убавит числа последующих перезаписей настолько, чтобы оправдать первый проход.

Обширное экспериментальное тестирование, выполненное М. А. Вайсом (М. А. Weiss) [Сотр. J. 34 (1991), 88-91], четко выявило, что среднее число перезаписей, выполняемых в ходе сортировки по алгоритму D при смещениях 2* - 1, ..., 15, 7, 3, 1, примерно пропорционально 7V/. Если быть более точным, Вайс показал, что Bave « 1.557V5/4 - 4.48ЛГ + 0(7V3/4) при 100 < 7V < 12000000, если используются эти смещения; эмпирическое стандартное отклонение составляло примерно .0657V/. Он также выяснил, что последовательность Седгевика (11) приводит к асимптотически более высокой производительности, Bave 0.437V/ + 18.5iV + 0(7V/). Удивительно, но стандартное отклонение для этой последовательности смещений оказалось довольно мало, примерно TV/.

В табл. 7 показаны типовые характеристики числа перезаписей, отнесенные к одному проходу, которые были получены в трех экспериментах со случайными данными. Использовалась последовательность смещений вида 2* - 1, 2* + 1 и (11). В каждом эксперименте использовались те же массивы данных. Общее число перезаписей Yls в этих экспериментах оказалась равным соответственно 346 152, 329 532 и 248 788, так что первенство в этих "соревнованиях" следует отдать последовательности (11).

Хотя с каждым новым экспериментом мы все глубже проникаем в тайны сортировки по алгоритму D, три десятилетия исследований не дали окончательного ответа на главный вопрос - какая последовательность смещений наилучшая. Если N меньше 1 ООО, самое простое правило наподобие

Положить Но = 1, = 3Hs + 1 и остановиться на Ht-i при 3ht > N (12)