00 01 02 03 П4 05 06 07 10

20 30 40 50 60 70 80

«4

Рис. 11. Соответствие между 2-упорядочением и путями на решетке. Курсивом набраны веса, соответствующие числу инверсий в 2-упорядоченной перестановке.

точку ([п/2], [n/2J), если выполнять очередной к-й шаг пути вправо или вниз в соответствии с тем, где находится к: в четной или нечетной позиции перестэг новки. Этим правилом определяется взаимно однозначное соответствие между 2-упорядоченными перестановками и п-шаговыми путями из одного угла решетчатой диаграммы в другой. Например, изображенный на рис. 11 путь соответствует перестановке

2 1 3 4 6 5 7 10 8 И 9 12 14 13 15. (1)

Далее, вертикальным отрезкам пути можно приписать веса, как показано на диаграмме; отрезку, ведущему из точки в точку приписывается вес г - j\. После несложных умозаключений читатель сможет убедиться в том, что сумма этих весов вдоль каждого пути равна числу инверсий в соответствующей перестановке; эта сумма также равна количеству заштрихованных квадратиков между данным путем и другим ступенчатым путем, выделенным на рисунке пунктирной линией с жирными точками (см. упр. 12). Так, например, перестановка (1) содержит 1-1-0 + 1-1-0 + 1-1-2-1-1-1-0 = 6 инверсий.

Если а < а и b < Ь, то число допустимых путей из (а, 6) в (а, 6) равно числу способов объединения а - а вертикальных отрезков с Ь - b горизонтальными, а и.менно

/а-а + Ь-Ь\ V а-а )

Следовательно, число перестановок, соответствующие пути которых проходят через вертикальный отрезок из в (i + l,j), равно

г + j\ fn-i - j -1\ i j V [n/2\-j )

Умножая это значение на вес данного отрезка и суммируя по всем отрезкам, получаем

0<j<n 0<j<n

Знаки абсолютной величины в этих суммах несколько усложняют вычисления, но в упр. 14 показано, что выражение для величины А„ имеет на удивление простой вид: [n/2J2""-. Следовательно, среднее число инверсий в случайной 2-упорядоченной перестановке равно

По формуле Стирлинга эта величина асимптотически приближается кл/тГ/Ттп/" х ОЛЬп. Как легко видеть, максимальное число инверсий равно

Ln/2J + 1\ 1 , 2 j~8"-

Полезно более тщательно проанализировать распределение числа инверсий, рассмотрев производящие функции

ui{z) = 1, h2{z) = l + Z,

hiz) = l + 2z, ""

h4{z) = l + 3z + z + z,

как в упр. 15. Таким образом найдем, что стандартное отклонение тоже пропорционально п/, так что число инверсий не слишко.ч устойчиво распределено около среднего значения.

Рассмотрим теперь общий случай алгоритма D с двумя проходами, когда смещения сортировки равны h и 1.

Теорема Н. Среднее число инверсий в h-уиорядоченной перестановке множества {1,2,... ,п} равно

где q = [n/h] и г = п mod h.

Эта теорема принадлежит Дугласу X. Ханту (Douglas Н. Hunt), [Bachelors thesis, Princeton University (April, 1967)]. Заметим, что формула справедлива и при h>n и дает верный результат: f{n,h) = \ {)-

Доказательство. В /i-упорядоченной перестановке содержится г упорядоченных подпоследовательностей длиной q + \ к h - г подпоследовательностей длиной q. Каждая инверсия образуется из элементов двух различных подпоследовательно-

стей, а каждая пара различных упорядоченных подпоследовательностей в случайной /г-упорядоченной перестановке определяет случайную 2-упорядоченную перестановку. Поэтому среднее число инверсий равно сумме средних значений числа инверсий во всех парах различных подпоследовательностей, а именно

. .,и -Wi . lit-Л М,

Следствие. Если последовательность смещений ht-i, ... ,hi,ho удовлетворяет условию

hs+i mod /is = О при t - 1 > s > О, (5)

то среднее число операций перезаписи в алгоритме D равно

{rj{q,+l,hs+i/hs) + ihs-rs)fiqs,h+i/hs)), (6)

i>s>0

где г« = Nmodhg, - [N/hs\, Ы = Nht-i, а функщш f определяется формулой (4).

Доказательство. Процесс /г«-сортировки предусматривает сортировку методом простых вставок (/г«+1 г«)-упорядоченныхподмассивов длиной qg + l и -г«) таких подмассивов длиной q. Поскольку предполагается, что исходная перестановка случайна и все ее элементы различны, то из условий делимости следует, что каждый из подмассивов - "случайная" (/гя+1 гя)-упорядоченная перестановка в том смысле, что все (/1в+1 г«)-упорядочениые перестановки равновероятны.

Условие (5) этого следствия всегда выполняется для двухпроходной сортировки методом Шелла, когда смещения равны соответственно /г и 1. Пусть q = [.Nlh\, а г = N mod h, тогда среднее значение величины В в программе D равно

г/(9+1, N) + {h- r)f{q,N) + f{N, Л) = + ) + + f{N,h).

В первом приближении функция f{n,h) равна {/ттjd>)n/h}; можно сравнить ее с гладкой кривой на рис. 12 при п = 64. Следовательно, время выполнения двухпроходной программы D примерно пропорционально

2N/h + fnNЧг.

Поэтому наилучшее значение h равно приблизительно 16N/-k « 1.72 v; при таком выборе h среднее время сортировки пропорционально 7V/.

Таким образом, применяя метод Шелла и используя всего-навсего два прохода, можно существенно сократить вре.мя по сравнению с методом простых вставок с 0{N) до 0(7V-). Ясно, что можно добиться лучших результатов, если использовать больше проходов. В упр. 18 обсуждается оптимальный выбор ht-i, ,ho при фиксированном t в случае, когда значения h ограничены условием делимости. Время выполнения при больших N сокращается до 0(7V-+/2), 1Д2 - 1). Используя приведенные выше формулы, барьер N преодолеть невозможно, потому что на последнем проходе в сумму инверсий всегда входит слагаемое