8 16 24 32 40 48 56 64 72 80

Рис. 12. Среднее число инверсий /(п, h) в Л-упорядоченном массиве из п элементов для случая п = 64.

Но интуиция подсказывает, что, если смещения ht-i,... ,ho не будут удовлетворять условию делимости (5), можно достичь большего. Например, при последовательном выполнении 8-, 4- и 2-сортировок невозможно взаимодействие между ключами в четных и нечетных позициях; поэтому на долю заключительной 1-сортировки останется Q(N) инверсий. В то же время при последовательном выполнении 7-, 5- и 3-сортировок массив перекомпоновывается так, что при заключительной 1-сортировке не может встретиться более 2N инверсий (см. упр. 26)! На самом деле наблюдается удивительное явление.

Теорема К. После h-сортировки к-упорядоченный массив остается к-упорядо-ченным.

Таким образом, массив, который был сначала 7-рассортированным, а потом 5-рассортированным, становится одновременно 7- и 5-упорядоченным. А если подвергнуть его 3-сортировке, то полученный массив будет 7-, 5- и 3-упорядоченным. Примеры проявления этого замечательного свойства можно найти в табл. 4.

Доказательство. В упр. 20 показано, что эта теорема вытекает из следующей леммы.

Лемма L. Пусть т., п, г - неотрицательные целые числа, а {x\,... ,Хга+г) и {у\,... ,Уп+г) - произвольные последовательности чисел, такие, что

У1<.Хт+1, У2<Хт+2, Уг<Хт+г- (7)

Если последовательности Хк и ук рассортировать независимо, так что х\ < • < Хт+г н J/1 < • • • < Уп+г, то соотношения (7) останутся в силе.

Доказательство. Известно, что все, кроме, быть может, m элементов последовательности Хк, превосходят (т. е. больше или равны) некоторые элементы последо-

вательности у, причем различные элементы Хк превосходят различные элементы у. Пусть 1 < j < г. Так как после сортировки элемент Xm+j превосходит т + j элементов Хк, то он превосходит, по крайней мере, j элементов ук, а значит, он превосходит j наименьших элементов у к- Следовательно, после сортировки имеем

Xm+j >Уз- I I

Из теоремы К видно, что при сортировке желательно пользоваться взаимно простыми значениями смещений, однако непосредственно из нее не следуют точные оценки числа перезаписей, выполняемых алгоритмом D. Так как число перестановок множества {1,2,...,п}, одновременно h- и А;-упорядоченных, не всегда является делителем п!, то понятно, что теорема К объясняет далеко не все; в результате А;-и /г-сортировок некоторые А;- и /г-упорядоченные массивы получаются чаще других. Более того, анализ усредненного варианта алгоритма D для общего случая смещений ht-i,. ..,ho при t>3 может поставить в тупик любого. Не существует даже очевидного способа отыскать "наихудший случай" для алгоритма D при произвольной последовательности смещений сортировки (/tt-i,..., Ло) и заданном N. Поэтому до сих пор все попытки анализа этого алгоритма в общем случае были тщетны. Но можно сделать определенные выводы из асимптотического поведения максимального времени сортировки, когда последовательность смещений имеет определенную форму.

Теорема Р. Если = 2*+ - 1 при О < s < t = [Ig TVJ, то время сортировки по алгоритму D есть 0{N/).

Доказательство. Достаточно найти оценку - числа перезаписей на s-m проходе, такую, чтобы Bt-\ + • • • + Pq = 0{N/). Для первых t/2 просмотров при t > S > t/2 можно воспользоваться очевидной оценкой Р« = 0{hs{N/hs)), а для последующих проходов можно применить результат упр. 23: Р« = 0{Nhs+2hs+i/hs). Следовательно, Bt-i + -- +Во = 0{N{2+2 + - .+2«/2+2«/2 + - • -+2)) = 0{N). \

Эта теорема принадлежит А. А. Папернову и Г. В. Стасевичу [Лроблемы передачи информации, 1,3 (1965), 81-98]. Она дает верхнюю оценку времени выполнения алгоритма в худшем случае, а не просто оценку среднего времени работы. Этот результат нетривиален, поскольку максимальное время выполнения в случае, когда смещения h удовлетворяют условию делимости (5), имеет порядок TV, а в упр. 24 доказано, чтб показатель 3/2 уменьшить нельзя.

Интересное улучшение по сравнению с теоремой Р обнаружил в 1969 году Воган Пратт (Vaughan Pratt). Если все смещения при сортировке выбираются из множества чисел вида 23, меньших N, то время выполнения алгоритма D будет порядка iV(logiV)-. В этом случае также можно внести в алгоритм несколько существенных упрощений. К сожалению, метод Пратта требует сравнительно большого числа проходов, так что это не лучший способ выбора смещений, если только N не очень велико (см. упр. 30 и 31). При реальных для практики значениях N наилучший набор значений смещений должен удовлетворять соотношению hg к р*, где параметр р W hg+i/hg можно в первом приближении считать независимым от s, но он существенно зависит от N.

Из изложенного выше очевидно, что было бы неразумно выбирать значения смещений, которые являются множителем всех предшественников. Но в то же время нельзя делать заключение, что наилучшие значения смещений - взаимно простые числа всех предшественников. Конечно, каждый элемент массива, который уже

gh- и 5А;-рассортирован, причем h ± к, имеет не более чем (/г - 1)(А; - 1) инверсий, когда наступает черед у-сортировки. (См. упр. 21.) Предложенная Праттом последовательность {23} имеет при 7V -> оо преимущество именно вследствие этого свойства, но оно не очень сказывается на практике, поскольку нарастает это преимущество довольно медленно.

Дж. Инсерпи (J. Incerpi) и Р. Седгевик (R. Sedgewick) [см. J. Сотр. Syst. Sci. 31 (1985), 210-224; а также Lecture Notes in Сотр. Sci. 1136 (1996), 1-11] изобрели способ выбора лучшего варианта в том и другом смысле. Они показали, как сформировать последовательность смещений, для которых hs » р*, причем каждый очередной элемент в последовательности является наибольшим общим делителем своих предшественников. Задав любое значение р > 1, они далее определяли базовую последовательность oi, ог, где Ок является наименьшим целым > р*, таким, что Uj ± Ofc при 1 < j < А;. Если, например, р = 2.5, базовая последовательность имеет вид

01, 02, аз,... = 3, 7, 16, 41, 101, 247, 613, 1529, 3821, 9539, .... После этого определяются смещения, если положить Ло = 1 и

hs = hs-rar "Р" (2) * - 2

Таким образом, начальный участок последовательности смещений принимает вид

1; ах; 02, ai02; охаз, 0203, 010203;----

Например, при р = 2.5 получим

1, 3, 7, 21, 48, 112, 336, 861, 1968, 4592, 13776, 33936, 86961, 198768, ....

Решающим фактором в этом построении является возможность обратить рекуррентное соотношение (8):

/г - 1\ /г\

h,=hr+s/ar = hr/a.y при \ j < s < j . (9)

Таким образом, пользуясь аргументами из предыдущего абзаца, получим, что число инверсий на элемент для ho-, /ii-сортировки и т. д. равно по крайней мере

Ь(о2, oi); 6(03,02), 6(03,01); 6(04, аз), 6(04, аг), 6(04, oi);..., (10)

где b{h,k) = i(/t - 1)(А; - 1). Если р~- < N < р, общее число перезаписей В не превосходит суммы первых t этой последовательности, умноженной на N. Отсюда можно доказать, что в худшем случае время сортировки имеет порядок, значительно лучший, чем 7V (см. упр. 41).

Теорема I. Время выполнения алгоритма D равно 0(7Уе"), если смещения hs определяются в соответствии с (8). Здесь с = vSlnp и константы в О зависят от р. I

Эта асимптотическая верхняя граница не имеет существенного значения при Л -> 00, поскольку последовательность, которую рекомендует Пратт, дает лучший результат. Рациональное же зерно теоремы I в том, что, если задано любое значение р > 1, последовательность смещений, имеющая практически показатель роста