\input style
\chapnotrue
\chapno=5
\subchno=2
\subsubchno=0
\alg D.(рАСПРЕДЕЛЯЮЩИЙ ПОДСЧЕТ.) эТОТ АЛГОРИТМ В ПРЕДПОЛОЖЕНИИ, ЧТО ВСЕ 
КЛЮЧИ---ЦЕЛЫЕ ЧИСЛА В ДИАПАЗОНЕ $u\le K_j\le v$ ПРИ $1\le j\le N$, СОРТИРУЕТ 
ЗАПИСИ $R_1$, \dots, $R_N$, ИСПОЛЬЗУЯ ВСПОМОГАТЕЛЬНУЮ ТАБЛИЦУ 
$|COUNT|[u]$, \dots, $|COUNT|[v]$. в КОНЦЕ РАБОТЫ АЛГОРИТМА ВСЕ ЗАПИСИ В 
ТРЕБУЕМОМ ПОРЯДКЕ ПЕРЕНОСЯТСЯ В ОБЛАСТЬ ВЫВОДА $S_1$, \dots, $S_N$.

\st[сБРОСИТЬ СЧЕТЧИКИ.] уСТАНОВИТЬ $|COUNT|[u]$, \dots, 
$|COUNT|[v]$ РАВНЫМИ НУЛЮ.

\st[цИКЛ ПО $j$.] вЫПОЛНИТЬ ШАГ \stp{3} ПРИ $1\le j\le N$,  ЗАТЕМ ПЕРЕЙТИ 
К ШАГУ \stp{4}.

\st[уВЕЛИЧИТЬ $|COUNT| [K_j]$.] уВЕЛИЧИТЬ ЗНАЧЕНИЕ $|COUNT|[K_j]$ НА 1.    

\st[сУММИРОВАНИЕ.] (к ЭТОМУ МОМЕНТУ ЗНАЧЕНИЕ $|COUNT|[i]$ ЕСТЬ ЧИСЛО 
КЛЮЧЕЙ, РАВНЫХ $i$.)  уСТАНОВИТЬ 
$|COUNT|[i]\asg COUNT[i]+COUNT[i-l]$ ПРИ $i=u+l$, $u+2$, \dots, $v$.

\st[цИКЛ ПО $j$.] (к ЭТОМУ МОМЕНТУ ЗНАЧЕНИЕ $|COUNT|[i]$ ЕСТЬ ЧИСЛО КЛЮЧЕЙ,
 МЕНЬШИХ ИЛИ РАВНЫХ $i$, В ЧАСТНОСТИ $|COUNT|[v]=N$.) вЫПОЛНИТЬ ШАГ 
\stp{6} ПРИ $j=N$, $N-1$, \dots, 1 И ЗАВЕРШИТЬ РАБОТУ АЛГОРИТМА.

\stp[вЫВОД $R_j$.] уСТАНОВИТЬ $i\asg |COUNT|[K_j]$, $S_i\asg R_i$, И 
$|COUNT| [K_j]\asg i-1$.
\algend
\noindent пРИМЕР ПРИМЕНЕНИЯ ЭТОГО АЛГОРИТМА ПРИВЕДЕН В УПР.~6; ПРОГРАММУ 
ДЛЯ МАШИНЫ \MIX\ МОЖНО НАЙТИ В УПР.~9. пРИ СФОРМУЛИРОВАННЫХ ВЫШЕ 
УСЛОВИЯХ ЭТО ОЧЕНЬ БЫСТРАЯ ПРОЦЕДУРА .СОРТИРОВКИ.

сОРТИРОВКА ПОСРЕДСТВОМ СРАВНЕНИЯ И ПОДСЧЕТА, КАК, В АЛГОРИТМЕ C, ВПЕРВЫЕ 
УПОМИНАЕТСЯ В РАБОТЕ э.~X.~фРЭНДА 
[{\sl JACM\/},{\bf 3} (1965), 152],. ХОТЯ ОН И НЕ ЗАЯВИЛ О НЕЙ КАК О СВОЕМ 
СОБСТВЕННОМ ИЗОБРЕТЕНИИ. рАСПРЕДЕЛЯЮЩИЙ ПОДСЧЕТ, КАК В АЛГОРИТМЕ D, 
ВПЕРВЫЕ РАЗРАБОТАН X.~сЬЮВОРДОМ В 1954~Г. И ИСПОЛЬЗОВАЛСЯ ПРИ ПОРАЗРЯДНОЙ 
СОРТИРОВКЕ, КОТОРУЮ МЫ ОБСУДИМ ПОЗЖЕ (СМ. П.~5.2.5); ЭТОТ МЕТОД ТАКЖЕ -БЫЛ 
ОПУБЛИКОВАН ПОД НАЗВАНИЕМ "Mathsort" В РАБОТЕ W. Feurzig, {\sl CACM\/}, 
{\bf 3} (I960), 601.

\excercises
\ex[15] бУДЕТ ЛИ РАБОТАТЬ АЛГОРИТМ с, ЕСЛИ В ШАГЕ с2 ЗНАЧЕНИЕ с 
БУДЕТ ИЗМЕНЯТЬСЯ ОТ $2$ ДО $N$, А НЕ ОТ $N$ ДО~$2$? чТО ПРОИЗОЙДЕТ, ЕСЛИ В 
ШАГЕ Cз ЗНАЧЕНИЕ $j$ БУДЕТ ИЗМЕНЯТЬСЯ ОТ $1$ ДО $i-1$?

\ex[21] пОКАЖИТЕ, ЧТО АЛГОРИТМ C РАБОТАЕТ ПРАВИЛЬНО И ПРИ 
НАЛИЧИИ ОДИНАКОВЫХ КЛЮЧЕЙ. еСЛИ $K_j=K_i$  И $j<i$, ТО ГДЕ ОКАЖЕТСЯ В 
КОНЦЕ КОНЦОВ $R_j$---ДО ИЛИ ПОСЛЕ $R_i$?

\rex[21] бУДЕТ ЛИ АЛГОРИТМ C РАБОТАТЬ ПРАВИЛЬНО, ЕСЛИ В ШАГЕ C4 ЗАМЕНИТЬ 
ПРОВЕРКУ "$K_i<K_j$"  НА "$K_i\le K_j$"?

\ex[16] нАПИШИТЕ \MIX-ПРОГРАММУ, КОТОРАЯ ЗАВЕРШИТ СОРТИРОВКУ, НАЧАТУЮ 
ПРОГРАММОЙ C; ВАША ПРОГРАММА ДОЛЖНА ПОМЕСТИТЬ КЛЮЧИ В ЯЧЕЙКИ $|OUTPUT|+1$, 
\dots, $|OUTPUT|+N$ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ. сКОЛЬКО ВРЕМЕНИ ЗАТРАТИТ НА 
ЭТО ВАША ПРОГРАММА?
%% 101

\ex[22] уЛУЧШИТСЯ ЛИ ПРОГРАММА C В РЕЗУЛЬТАТЕ СЛЕДУЮЩИХ ИЗМЕНЕНИЙ?
$$
\indent\vtop{
\halign{#\bskip\hfill&\bskip |#|\hfill&|#|\hfill\cr
вВЕСТИ НОВУЮ СТРОКУ 8А:  & INCX  & 0, 2 \cr
иЗМЕНИТЬ СТРОКУ 10:      & JGE    &5F\cr
иЗМЕНИТЬ СТРОКУ 14:      & DECX &1\cr
иСКЛЮЧИТЬ СТРОКУ 15. \cr
}
}
$$


\ex[18] пРОМОДЕЛИРУЙТЕ ВРУЧНУЮ РАБОТУ АЛГОРИТМА D,  ПОКАЗЫВАЯ 
ПРОМЕЖУТОЧНЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧАЮЩИЕСЯ ПРИ СОРТИРОВКЕ 16 ЗАПИСЕЙ
$$
\hbox{5т, 0с, 5U, 00, 9, 1N, 8S, 2R, 6A, 4A, 1G, 5L, 6T, 61, 70, 7N.}
$$
зДЕСЬ ЦИФРЫ---ЭТО КЛЮЧИ, А БУКВЫ---СОПУТСТВУЮЩАЯ ИНФОРМАЦИЯ В ЗАПИСЯХ.

\ex[13] яВЛЯЕТСЯ ЛИ АЛГОРИТМ D АЛГОРИТМОМ "УСТОЙЧИВОЙ" СОРТИРОВКИ? 
\ex[15] бУДЕТ ЛИ АЛГОРИТМ D РАБОТАТЬ ПРАВИЛЬНО, ЕСЛИ В ШАГЕ D5 ЗНАЧЕНИЕ 
$j$ БУДЕТ ИЗМЕНЯТЬСЯ ОТ $1$ ДО $N$, А НЕ ОТ $N$ ДО $1$?

\ex[23] нАПИШИТЕ \MIX-ПРОГРАММУ ДЛЯ АЛГОРИТМА D, АНАЛОГИЧНУЮ ПРОГРАММЕ C 
И УПР.~4. вЫРАЗИТЕ ВРЕМЯ РАБОТЫ ВАШЕЙ ПРОГРАММЫ В ВИДЕ ФУНКЦИИ ОТ $N$ И $(v-u)$.

\ex[25] пРЕДЛОЖИТЕ ЭФФЕКТИВНЫЙ АЛГОРИТМ, КОТОРЫЙ БЫ ЗАМЕНЯЛ $N$ ВЕЛИЧИН 
$(R_1, \dots, R_N)$ СООТВЕТСТВЕННО НА $(R_{p(1)}, \dots, R_{p(1)}))$, ЕСЛИ 
ДАНЫ ЗНАЧЕНИЯ $R_1$, \dots, $R_N$ И ПЕРЕСТАНОВКА $p(1)$ \dots $p (N)$ 
МНОЖЕСТВА 
$\{1, \dots,  N\}$. пОСТАРАЙТЕСЬ НЕ ИСПОЛЬЗОВАТЬ ИЗЛИШНЕГО ПРОСТРАНСТВА 
ПАМЯТИ. (эТА ЗАДАЧА ВОЗНИКАЕТ, КОГДА ТРЕБУЕТСЯ ПЕРЕРАЗМЕСТИТЬ В ПАМЯТИ 
ЗАПИСИ ПОСЛЕ СОРТИРОВКИ ТАБЛИЦЫ АДРЕСОВ, НЕ РАСХОДУЯ ПАМЯТЬ НА $2N$ ЗАПИСЕЙ.)

\ex[M27] нАПИШИТЕ \MIX-ПРОГРАММУ ДЛЯ АЛГОРИТМА ИЗ УПР.~10 И 
ПРОАНАЛИЗИРУЙТЕ ЕЕ. ЭФФЕКТИВНОСТЬ.

\rex[25] пРЕДЛОЖИТЕ ЭФФЕКТИВНЫЙ АЛГОРИТМ ПЕРЕРАЗМЕЩЕНИЯ В ПАМЯТИ ЗАПИСЕЙ 
$R_1$, \dots, $R_N$ В ОТСОРТИРОВАННОМ ПОРЯДКЕ ПОСЛЕ ЗАВЕРШЕНИЯ СОРТИРОВКИ 
СПИСКА (РИС.~7). пОСТАРАЙТЕСЬ НЕ ИСПОЛЬЗОВАТЬ ИЗЛИШНЕГО ПРОСТРАНСТВА ПАМЯТИ.

\rex[27] аЛГОРИТМУ D ТРЕБУЕТСЯ  ПРОСТРАНСТВО ДЛЯ $2N$ ЗАПИСЕЙ 
$R_1$, \dots $R_N$  И $S_1$, \dots, $S_N$. пОКАЖИТЕ, ЧТО МОЖНО ОБОЙТИСЬ 
ПРОСТРАНСТВОМ ДЛЯ $N$ ЗАПИСЕЙ $R_1$, \dots, $R_N$, ЕСЛИ ВМЕСТО ШАГОВ D5 И 
D6 ПОДСТАВИТЬ НОВУЮ УПОРЯДОЧИВАЮЩУЮ ПРОЦЕДУРУ. (тАКИМ ОБРАЗОМ, ЗАДАЧА 
СОСТОИТ В ТОМ, ЧТОБЫ РАЗРАБОТАТЬ АЛГОРИТМ, КОТОРЫЙ БЫ ПЕРЕРАЗМЕЩАЛ ЗАПИСИ 
$R_1$, \dots, $R_N$.  ОСНОВЫВАЯСЬ НА ЗНАЧЕНИЯХ
$$
|COUNT| [u], \ldots |COUNT| [v]
$$
ПОСЛЕ ВЫПОЛНЕНИЯ ШАГА D4, НЕ ИСПОЛЬЗУЯ ДОПОЛНИТЕЛЬНОЙ ПАМЯТИ; ЭТО, 
ПО СУЩЕСТВУ, ОБОБЩЕНИЕ ЗАДАЧИ, РАССМОТРЕННОЙ В УПР. 10.)

\subsubchap{сОРТИРОВКА ВСТАВКАМИ} % 5.2.1
оДНО ИЗ ВАЖНЫХ СЕМЕЙСТВ-МЕТОДОВ СОРТИРОВКИ ОСНОВАНО НА УПОМЯНУТОМ В 
НАЧАЛЕ \S~5.2 СПОСОБЕ, КОТОРЫМ ПОЛЬЗУЮТСЯ ИГРОКИ В БРИДЖ; ПРЕДПОЛАГАЕТСЯ, 
ЧТО ПЕРЕД РАССМОТРЕНИЕМ ЗАПИСИ $R_j$ ПРЕДЫДУЩИЕ ЗАПИСИ $R_1$, \dots, 
$R_{j-1}$ УЖЕ УПОРЯДОЧЕНЫ, И $R_j$ ВСТАВЛЯЕТСЯ В СООТВЕТСТВУЮЩЕЕ МЕСТО. нА 
ОСНОВЕ ЭТОЙ СХЕМЫ ВОЗМОЖНЫ НЕСКОЛЬКО ЛЮБОПЫТНЫХ ВАРИАЦИЙ.

\section пРОСТЫЕ ВСТАВКИ. пРОСТЕЙШАЯ СОРТИРОВКА ВСТАВКАМИ ОТНОСИТСЯ К 
НАИБОЛЕЕ ОЧЕВИДНЫМ. пУСТЬ $1 <j  \le  N$  И  ЗАПИСИ $R_1$, \dots, $R_{j-1}$
%% 102
УЖЕ РАЗМЕЩЕНЫ ТАК, ЧТО
$$
K_1\le K_2\le \ldots \le K_{j-1}.
$$
(нАПОМНИМ, ЧТО В ЭТОЙ ГЛАВЕ ЧЕРЕЗ $K_j$ ОБОЗНАЧАЕТСЯ КЛЮЧ ЗАПИСИ $R_j$.) 
бУДЕМ СРАВНИВАТЬ ПО ОЧЕРЕДИ $K_j$ С $K_{j-1}$, $K_{j-2}$, \dots ДО ТЕХ ПОР, 
ПОКА НЕ ОБНАРУЖИМ, ЧТО ЗАПИСЬ $R_j$ СЛЕДУЕТ ВСТАВИТЬ МЕЖДУ $R_i$ И 
$R_{i+1}$; ТОГДА ПОДВИНЕМ ЗАПИСИ $R_{i+1}$, \dots, $R_{j-1}$ НА ОДНО МЕСТО 
ВВЕРХ И ПОМЕСТИМ НОВУЮ ЗАПИСЬ В ПОЗИЦИЮ $i+1$. уДОБНО СОВМЕЩАТЬ ОПЕРАЦИИ 
СРАВНЕНИЯ И ПЕРЕМЕЩЕНИЯ, ПЕРЕМЕЖАЯ ИХ ДРУГ С ДРУГОМ, КАК ПОКАЗАНО В 
СЛЕДУЮЩЕМ АЛГОРИТМЕ; ПОСКОЛЬКУ ЗАПИСЬ $R_j$ КАК БЫ "ПРОНИКАЕТ НА 
ПОЛОЖЕННЫЙ ЕЙ УРОВЕНЬ", ЭТОТ СПОСОБ ЧАСТО НАЗЫВАЮТ \dfn{ПРОСЕИВАНИЕМ}, 
ИЛИ \dfn{ПОГРУЖЕНИЕМ}.

\alg S.(сОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ.) зАПИСИ $R_1$, \dots,  $R_N$ 
ПЕРЕРАЗМЕЩАЮТСЯ НА ТОМ ЖЕ МЕСТЕ; ПОСЛЕ ЗАВЕРШЕНИЯ СОРТИРОВКИ ИХ КЛЮЧИ 
БУДУТ УПОРЯДОЧЕНЫ: $K_1\le \ldots \le K_N$.

\st[цИКЛ. ПО $j$.] вЫПОЛНИТЬ ШАГИ ОТ \stp{2} ДО \stp{5} ПРИ  $j= 2$, 3, 
\dots, $N$ И ПОСЛЕ ЭТОГО ЗАВЕРШИТЬ АЛГОРИТМ.
\picture{рИС. 10.  аЛГОРИТМ S: ПРОСТЫЕ ВСТАВКИ.}
\st[уСТАНОВИТЬ $i$, $K$, $R$.] уСТАНОВИТЬ $i\asg j-1$,  $K\asg K_j$,  
$R\asg R_j$.(в ПОСЛЕДУЮЩИХ ШАГАХ МЫ ПОПЫТАЕМСЯ ВСТАВИТЬ ЗАПИСЬ $R$ В 
НУЖНОЕ МЕСТО, СРАВНИВАЯ $K$ С $K_i$ ПРИ УБЫВАЮЩИХ ЗНАЧЕНИЯХ $i$.)

\st[сРАВНИТЬ $K$ С  $K_i$.] еСЛИ $K\ge K_i$, ТО ПЕРЕЙТИ К ШАГУ  
\stp{5}. (мЫ НАШЛИ ИСКОМОЕ МЕСТО ДЛЯ ЗАПИСИ $R$.)

\st[пЕРЕМЕСТИТЬ $R_i$, УМЕНЬШИТЬ $i$.] уСТАНОВИТЬ $R_{i+1}\asg R_i$,
 $i\asg i-1$. еСЛИ $i>0$, ТО ВЕРНУТЬСЯ К ШАГУ \stp{3}. (еСЛИ $i=0$, ТО 
$K$---НАИМЕНЬШИЙ ИЗ РАССМОТРЕННЫХ ДО СИХ ПОР КЛЮЧЕЙ, А, ЗНАЧИТ, ЗАПИСЬ $R$ 
ДОЛЖНА ЗАНЯТЬ ПЕРВУЮ ПОЗИЦИЮ.)
\st[$R$ НА МЕСТО $R_{i+1}$.] уСТАНОВИТЬ $R_{i+1}\asg R$.
\algend
в ТАБЛ.~1 ПОКАЗАНО ПРИМЕНЕНИЕ АЛГОРИТМА S К ШЕСТНАДЦАТИ ЧИСЛАМ, ВЗЯТЫМ 
НАМИ ДЛЯ ПРИМЕРОВ. эТОТ МЕТОД ЧРЕЗВЫЧАЙНО ПРОСТО РЕАЛИЗУЕТСЯ НА 
ВЫЧИСЛИТЕЛЬНОЙ МАШИНЕ; ФАКТИЧЕСКИ СЛЕДУЮЩАЯ \MIX-ПРОГРАММА---САМАЯ 
КОРОТКАЯ ИЗ ВСЕХ ПРИЕМЛЕМЫХ ПРОГРАММ СОРТИРОВКИ В ЭТОЙ КНИГЕ.
%% 103

\prog S.(сОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ). зАПИСИ, КОТОРЫЕ НАДО 
ОТСОРТИРОВАТЬ, НАХОДЯТСЯ В ЯЧЕЙКАХ $|INPUT|+1$, \dots,  $|INPUT|+N$; ОНИ 
СОРТИРУЮТСЯ В ТОЙ ЖЕ ОБЛАСТИ ПО КЛЮЧУ, ЗАНИМАЮЩЕМУ ОДНО СЛОВО ЦЕЛИКОМ. 
зДЕСЬ $|rI1|\equiv j-N$; $|rI2|\equiv i$, $|rA|\equiv R\equiv K$; 
ПРЕДПОЛАГАЕТСЯ, ЧТО $N\ge 2$.
\code
START &ENT1 &2-N       &1      & S1.цИКЛ no $j$. $j\asg 2$. 
2H    &LDA  &INPUT+N,1 &N-1    & S2. уСТАНОВИТЬ $i$, $K$, $R$
      &ENT2 &N-1,1     &N-1    & $i\asg j-1$.
3H    &CMPA &INPUT,2   &B+N-1-A& S3. сРАВНИТЬ $K$, $K_i$
      &JGE  &5F        &B+N-1-A& к S5, ЕСЛИ $K\ge K_i$.
4H    &LDX  &INPUT,2   &в      & S4. пЕРЕМЕСТИТЬ $R_i$, УМЕНЬШИТЬ $i$
      &STX  &INPUT+1,2 &в      & $R_{i+1}\asg R_i$.
      &DEC2 &1         &B      & $i\asg i-1$.
      &J2P  &3B        &B      & к S3, ЕСЛИ $i>0$.
5H    &STA  &INPUT+1,2 &N-1    & S5. $R$ НА МЕСТО $R_i+1$.
      &INC1 &1         &N-1
      &J1NP &2B        &N-1    & $2\le j \le N$.
\endcode
\progend
вРЕМЯ РАБОТЫ ЭТОЙ ПРОГРАММЫ РАВНО $9B+10N-3A-9$ ЕДИНИЦ, ГДЕ $N$---ЧИСЛО 
СОРТИРУЕМЫХ ЗАПИСЕЙ, $A$---ЧИСЛО СЛУЧАЕВ, КОГДА В ШАГЕ S4 ЗНАЧЕНИЕ $i$ 
УБЫВАЕТ ДО 0, А $B$---ЧИСЛО ПЕРЕМЕЩЕНИЙ. яСНО, ЧТО $A$ РАВНО ЧИСЛУ СЛУЧАЕВ, 
КОГДА $K_j<(K_1, \ldots, K_{j-1})$ ПРИ $1< j \le N$, Т. Е. ЭТО ЧИСЛО 
ЛЕВОСТОРОННИХ МИНИМУМОВ---ВЕЛИЧИНА, КОТОРАЯ БЫЛА ТЩАТЕЛЬНО ИССЛЕДОВАНА В 
П.~1.2.10. нЕМНОГО ПОДУМАВ, НЕТРУДНО ПОНЯТЬ, ЧТО $B$---ТОЖЕ ИЗВЕСТНАЯ 
ВЕЛИЧИНА: ЧИСЛО ПЕРЕМЕЩЕНИЙ ПРИ ФИКСИРОВАННОМ $j$ РАВНО ЧИСЛУ ИНВЕРСИЙ 
КЛЮЧА $K_j$, ТАК ЧТО $B$ РАВНО ЧИСЛУ ИНВЕРСИЙ ПЕРЕСТАНОВКИ $K_1$, $K_2$, 
\dots, $K_N$. сЛЕДОВАТЕЛЬНО, СОГЛАСНО ФОРМУЛАМ (1.2.10--16) И (5.1.1--12, 
13),
$$
\eqalign{
A&=(\min 0, \ave H_N-1, \max N-1,  \dev\sqrt{H_n-H_n^{(2)}});\cr
B&=(\min 0, \ave (N^2-N)/4, \max (N^2-N)/2,
\dev\sqrt{N(N-1)(N+2.5)/6}),\cr
}
$$
А СРЕДНЕЕ ВРЕМЯ РАБОТЫ ПРОГРАММЫ S В ПРЕДПОЛОЖЕНИИ, ЧТО КЛЮЧИ РАЗЛИЧНЫ И 
РАСПОЛОЖЕНЫ В СЛУЧАЙНОМ ПОРЯДКЕ, РАВНО $(2.25N^2+7.75N-3H_N-6)u$. в 
УПР.~33 ПОКАЗАНО, КАК МОЖНО ЧУТЬ-ЧУТЬ УМЕНЬШИТЬ ЭТО ВРЕМЯ.

пРИВЕДЕННЫЕ В КАЧЕСТВЕ ПРИМЕРА В ТАБЛ.~1 ДАННЫЕ СОДЕРЖАТ 16~ЭЛЕМЕНТОВ; 
ИМЕЮТСЯ ДВА ЛЕВОСТОРОННИХ МИНИМУМА, 087 И~061, И, КАК МЫ ВИДЕЛИ В 
ПРЕДЫДУЩЕМ ПУНКТЕ, 41 ИНВЕРСИЯ. сЛЕДОВАТЕЛЬНО, $N=16$, $A=2$, $B=41$, А 
ОБЩЕЕ ВРЕМЯ СОРТИРОВКИ РАВНО $514u$.

\section бИНАРНЫЕ ВСТАВКИ И ДВУХПУТЕВЫЕ ВСТАВКИ. кОГДА ПРИ 
СОРТИРОВКЕ ПРОСТЫМИ ВСТАВКАМИ ОБРАБАТЫВАЕТСЯ $j$-Я ЗАПИСЬ, ЕЕ КЛЮЧ 
СРАВНИВАЕТСЯ В СРЕДНЕМ ПРИМЕРНО С $j/2$ РАНЕЕ ОТСОРТИРОВАННЫМИ КЛЮЧАМИ; 
%% 104
{\catcode`\!=\active\def!{\hidewidth{}_{\hbox{\tentt\char"5E}}}
 \catcode`\@=\active\def@{{}_{\hbox{\tentt\char"5E}}\hidewidth}
 \catcode`\:=\active\def:{\hidewidth{\char`\:}}
\ctable{\bskip$#$\bskip&&\bskip$#$\bskip\cr
\noalign{\rightline{тАБЛИЦА 1}}
\noalign{\centerline{пРИМЕР ПРИМЕНЕНИЯ ПРОСТЫХ ВСТАВОК}}
!503&:087 &\cr
 087& 503@&:512\cr
!087& 503 & 512 &:061\cr
 061& 087 & 503 & 512@&:908\cr
 061& 087@& 503 & 512 & 908 &:170\cr
 061& 087 & 170 & 503 & 512@& 908 &:897\cr
\noalign{\line{\null\leaders\hbox to 1em{\hss.\hss}\hfill\null}}\cr
 061& 087 & 154 & 170 & 275 &426 &503 &509 &512 &612 &653 &677@&765 &897 &908 &:703\cr
 061& 087 & 154 & 170 & 275 &426 &503 &509 &512 &612 &653 &677 &703 &765 &897 & 908\cr
}
}
ПОЭТОМУ ОБЩЕЕ ЧИСЛО СРАВНЕНИЙ РАВНО 
ПРИБЛИЗИТЕЛЬНО $(1+2+\cdots+N)/2\approx N^2/4$, А ЭТО ОЧЕНЬ МНОГО, ДАЖЕ 
ЕСЛИ $N$ УМЕРЕННО ВЕЛИКО. в П.~6.2.1 МЫ ИЗУЧИМ МЕТОДЫ "БИНАРНОГО ПОИСКА",
 КОТОРЫЕ УКАЗЫВАЮТ, КУДА ВСТАВЛЯТЬ $j$-Й ЭЛЕМЕНТ ПОСЛЕ ПРИБЛИЗИТЕЛЬНО 
$\log_2 j$ СООТВЕТСТВУЮЩИМ ОБРАЗОМ ВЫБРАННЫХ СРАВНЕНИЙ. нАПРИМЕР, ЕСЛИ 
ВСТАВЛЯЕТСЯ 64-Я ЗАПИСЬ, МОЖНО СНАЧАЛА СРАВНИТЬ КЛЮЧ $K_{64}$ С 
$K_{32}$; ЗАТЕМ, ЕСЛИ ОН МЕНЬШЕ, СРАВНИВАЕМ ЕГО С $K_{16}$, ЕСЛИ БОЛЬШЕ---С 
$K_{48}$ И Т. Д., ТАК ЧТО МЕСТО ДЛЯ $R_{64}$ БУДЕТ НАЙДЕНО ПОСЛЕ ВСЕГО 
ЛИШЬ ШЕСТИ СРАВНЕНИЙ. оБЩЕЕ ЧИСЛО СРАВНЕНИЙ ДЛЯ $N$ ВСТАВЛЯЕМЫХ ЭЛЕМЕНТОВ 
РАВНО ПРИБЛИЗИТЕЛЬНО $N \log_2 N$, ЧТО СУЩЕСТВЕННО ЛУЧШЕ, ЧЕМ $N^2/4$; В 
П.~6.2.1 ПОКАЗАНО, ЧТО СООТВЕТСТВУЮЩАЯ ПРОГРАММА НЕ ОБЯЗАТЕЛЬНО НАМНОГО 
СЛОЖНЕЕ, ЧЕМ ПРОГРАММА ДЛЯ ПРОСТЫХ ВСТАВОК. эТОТ МЕТОД НАЗЫВАЕТСЯ 
\dfn{БИНАРНЫМИ ВСТАВКАМИ}. оН УПОМИНАЛСЯ дЖОНОМ мОЧЛИ ЕЩЕ В 1946~Г., В 
ПЕРВОЙ ПУБЛИКАЦИИ ПО МАШИННОЙ СОРТИРОВКЕ.

нЕПРИЯТНОСТЬ СОСТОИТ В ТОМ, ЧТО БИНАРНЫЕ ВСТАВКИ РЕШАЮТ ЗАДАЧУ ТОЛЬКО 
НАПОЛОВИНУ: 
ПОСЛЕ ТОГО, КАК МЫ НАШЛИ, КУДА  ВСТАВЛЯТЬ ЗАПИСЬ $R_j$, ВСЕ 
РАВНО НУЖНО ПОДВИНУТЬ ПРИМЕРНО $j/2$ РАНЕЕ ОТСОРТИРОВАННЫХ ЗАПИСЕЙ, ЧТОБЫ 
ОСВОБОДИТЬ МЕСТО ДЛЯ $R_j$ ТАК ЧТО ОБЩЕЕ ВРЕМЯ РАБОТЫ ОСТАЕТСЯ, ПО 
СУЩЕСТВУ, ПРОПОРЦИОНАЛЬНЫМ $N_2$. нЕКОТОРЫЕ ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ 
(НАПРИМЕР, IBM 705) ИМЕЮТ ВСТРОЕННЫЕ ИНСТРУКЦИИ "ПЕРЕБРОСКИ", 
ВЫПОЛНЯЮЩИЕ ОПЕРАЦИИ ПЕРЕМЕЩЕНИЯ С БОЛЬШОЙ СКОРОСТЬЮ, НО С РОСТОМ $N$ 
ЗАВИСИМОСТЬ ОТ $N^2$ В КОНЦЕ КОНЦОВ НАЧИНАЕТ ПРЕОБЛАДАТЬ, нАПРИМЕР, АНАЛИЗ,
 ПРОВЕДЕННЫЙ X. нЭГДЕРОМ 
[{\sl CACM\/}, {\bf 3} (1960), 618--620],
ПОКАЗЫВАЕТ, ЧТО НЕ СЛЕДУЕТ РЕКОМЕНДОВАТЬ БИНАРНЫЕ ВСТАВКИ ПРИ СОРТИРОВКЕ 
БОЛЕЕ $N=128$ ЗАПИСЕЙ НА МАШИНЕ IBM~705, ЕСЛИ КАЖДАЯ ЗАПИСЬ СОСТОИТ ИЗ 80 
ЛИТЕР; АНАЛОГИЧНЫЙ АНАЛИЗ ПРИМЕНИМ И К ДРУГИМ МАШИНАМ.
%% 105
{
\catcode`\!=\active\def!{\hidewidth{}_{\hbox{\tentt\char"5E}}}
 \catcode`\@=\active\def@{{}_{\hbox{\tentt\char"5E}}\hidewidth}
 \catcode`\:=\active\def:{\hidewidth{\char`\:}}
\ctable{\bskip$#$\bskip&&\bskip$#$\bskip\cr
\noalign{\rightline{тАБЛИЦА 2}}
\noalign{\centerline{дВУХПУТЕВЫЕ ВСТАВКИ}}
   &   &   &     &!503 \cr
   &   &   & 087 & 503@ \cr
   &   &   &!087 & 503 &512 \cr
   &   &061& 087 & 503 &512@ \cr
   &   &061& 087@& 503 &512 & 908 \cr
   &061&087& 170 & 503 &512 &@908 \cr
   &061&087& 170@& 503 &512 & 897 & 908 \cr
061&087&170& 276 & 503 &512 & 897 & 908 \cr
}
}

рАЗУМЕЕТСЯ, ИЗОБРЕТАТЕЛЬНЫЙ ПРОГРАММИСТ МОЖЕТ ПРИДУМАТЬ КАКИЕ-НИБУДЬ 
СПОСОБЫ, ПОЗВОЛЯЮЩИЕ СОКРАТИТЬ ЧИСЛО НЕОБХОДИМЫХ ПЕРЕМЕЩЕНИЙ; ПЕРВЫЙ 
ТАКОЙ ПРИЕМ, ПРЕДЛОЖЕННЫЙ В НАЧАЛЕ 50-Х ГОДОВ, ПРОИЛЛЮСТРИРОВАН В 
ТАБЛ.~2. зДЕСЬ ПЕРВЫЙ - ЭЛЕМЕНТ ПОМЕЩАЕТСЯ В СЕРЕДИНУ ОБЛАСТИ ВЫВОДА, И 
МЕСТО ДЛЯ ПОСЛЕДУЮЩИХ ЭЛЕМЕНТОВ ОСВОБОЖДАЕТСЯ ПРИ ПОМОЩИ СДВИГОВ ВЛЕВО ИЛИ 
ВПРАВО, ТУДА, КУДА УДОБНЕЕ. тАКИМ ОБРАЗОМ УДАЕТСЯ СЭКОНОМИТЬ ПРИМЕРНО 
ПОЛОВИНУ ВРЕМЕНИ РАБОТЫ ПО СРАВНЕНИЮ С ПРОСТЫМИ ВСТАВКАМИ ЗА СЧЕТ 
НЕКОТОРОГО УСЛОЖНЕНИЯ ПРОГРАММЫ. мОЖНО ПРИМЕНЯТЬ ЭТОТ МЕТОД, ИСПОЛЬЗУЯ НЕ 
БОЛЬШЕ ПАМЯТИ, ЧЕМ ТРЕБУЕТСЯ ДЛЯ $N$ ЗАПИСЕЙ (СМ. УПР. 6), НО МЫ НЕ СТАНЕМ 
ДОЛЬШЕ ЗАДЕРЖИВАТЬСЯ НА ТАКИХ "ДВУХПУТЕВЫХ" ВСТАВКАХ, ТАК КАК 
БЫЛИ РАЗРАБОТАНЫ ГОРАЗДО БОЛЕЕ ИНТЕРЕСНЫЕ МЕТОДЫ.

\section мЕТОД шЕЛЛА. дЛЯ АЛГОРИТМА СОРТИРОВКИ, КОТОРЫЙ КАЖДЫЙ 
РАЗ ПЕРЕМЕЩАЕТ ЗАПИСЬ ТОЛЬКО НА ОДНУ ПОЗИЦИЮ, СРЕДНЕЕ ВРЕМЯ РАБОТЫ БУДЕТ В 
ЛУЧШЕМ СЛУЧАЕ ПРОПОРЦИОНАЛЬНО $N^2$, ПОТОМУ ЧТО В ПРОЦЕССЕ СОРТИРОВКИ 
КАЖДАЯ ЗАПИСЬ ДОЛЖНА ПРОЙТИ В СРЕДНЕМ ЧЕРЕЗ $N/3$ ПОЗИЦИЙ (СМ. УПР.~7). 
пОЭТОМУ, ЕСЛИ МЫ ХОТИМ ПОЛУЧИТЬ МЕТОД, СУЩЕСТВЕННО ПРЕВОСХОДЯЩИЙ ПО 
СКОРОСТИ ПРОСТЫЕ ВСТАВКИ, ТО НЕОБХОДИМ НЕКОТОРЫЙ МЕХАНИЗМ, С ПОМОЩЬЮ 
КОТОРОГО ЗАПИСИ МОГЛИ БЫ ПЕРЕМЕЩАТЬСЯ БОЛЬШИМИ СКАЧКАМИ, А НЕ КОРОТКИМИ ШАЖКАМИ.

тАКОЙ МЕТОД ПРЕДЛОЖЕН В 1959~Г. дОНАЛЬДОМ л. шЕЛЛОМ [{\sl CACM\/}, {\bf 2} 
(July, 1959), 30--32]; МЫ БУДЕМ НАЗЫВАТЬ ЕГО \dfn{СОРТИРОВКОЙ С УБЫВАЮЩИМ 
ШАГОМ}. в ТАБЛ.~3 ПРОИЛЛЮСТРИРОВАНА ОБЩАЯ ИДЕЯ, ЛЕЖАЩАЯ В ОСНОВЕ ЭТОГО 
МЕТОДА. сНАЧАЛА ДЕЛИМ 16 ЗАПИСЕЙ НА 8 ГРУПП ПО ДВЕ ЗАПИСИ В КАЖДОЙ 
ГРУППЕ: $(R_1, R_9)$, $(R_2, R_{10})$, \dots, $(R_8, R_{16})$. в 
РЕЗУЛЬТАТЕ СОРТИРОВКИ КАЖДОЙ ГРУППЫ ЗАПИСЕЙ ПО ОТДЕЛЬНОСТИ ПРИХОДИМ КО 
ВТОРОЙ СТРОКЕ ТАБЛ. 3,
%% 106
\picture{тАБЛИЦА 3}
ЭТО НАЗЫВАЕТСЯ "ПЕРВЫМ ПРОСМОТРОМ". зАМЕТИМ, ЧТО ЭЛЕМЕНТЫ 154 И 512 
ПОМЕНЯЛИСЬ МЕСТАМИ, А 908 И 897 ПЕРЕМЕСТИЛИСЬ ВПРАВО. рАЗДЕЛИМ ТЕПЕРЬ 
ЗАПИСИ НА ЧЕТЫРЕ ГРУППЫ ПО ЧЕТЫРЕ В КАЖДОЙ:
$(R_1, R_5, R_9, R_{13})$, \dots, $(R_4, R_8, R_{12}, R_{16})$---И ОПЯТЬ 
ОТСОРТИРУЕМ КАЖДУЮ ГРУППУ В ОТДЕЛЬНОСТИ; ЭТОТ ВТОРОЙ ПРОСМОТР ПРИВОДИТ К 
ТРЕТЬЕЙ СТРОКЕ ТАБЛИЦЫ. пРИ ТРЕТЬЕМ ПРОСМОТРЕ СОРТИРУЮТСЯ ДВЕ ГРУППЫ ПО 
ВОСЕМЬ ЗАПИСЕЙ; ПРОЦЕСС ЗАВЕРШАЕТСЯ ЧЕТВЕРТЫМ ПРОСМОТРОМ, ВО ВРЕМЯ 
КОТОРОГО СОРТИРУЮТСЯ ВСЕ 16 ЗАПИСЕЙ. в КАЖДОМ ИЗ ЭТИХ ПРОМЕЖУТОЧНЫХ 
ПРОЦЕССОВ СОРТИРОВКИ УЧАСТВУЮТ ЛИБО СРАВНИТЕЛЬНО КОРОТКИЕ ФАЙЛЫ, ЛИБО 
УЖЕ СРАВНИТЕЛЬНО ХОРОШО УПОРЯДОЧЕННЫЕ ФАЙЛЫ, ПОЭТОМУ НА КАЖДОМ 
ЭТАПЕ МОЖНО ПОЛЬЗОВАТЬСЯ ПРОСТЫМИ ВСТАВКАМИ; ЗАПИСИ ДОВОЛЬНО 
БЫСТРО ДОСТИГАЮТ СВОЕГО КОНЕЧНОГО ПОЛОЖЕНИЯ.

пОСЛЕДОВАТЕЛЬНОСТЬ ШАГОВ 8, 4, 2, 1 НЕ СЛЕДУЕТ СЧИТАТЬ НЕЗЫБЛЕМОЙ, МОЖНО 
ПОЛЬЗОВАТЬСЯ \emph{ЛЮБОЙ} ПОСЛЕДОВАТЕЛЬНОСТЬЮ $h_t$, $h_{t-1}$, \dots, 
$h_1$, В КОТОРОЙ ПОСЛЕДНИЙ ШАГ $h_1$ РАВЕН 1. нАПРИМЕР, В ТАБЛ.~4 БУДЕТ 
ПОКАЗАНА СОРТИРОВКА ТЕХ ЖЕ ДАННЫХ С ШАГАМИ 7, 5, 3, 1. оДНИ 
ПОСЛЕДОВАТЕЛЬНОСТИ ОКАЗЫВАЮТСЯ ГОРАЗДО ЛУЧШЕ ДРУГИХ; МЫ ОБСУДИМ ВЫБОР 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ ШАГОВ ПОЗЖЕ.

\alg D.(сОРТИРОВКА С УБЫВАЮЩИМ ШАГОМ.) зАПИСИ $R_1$, \dots, 
$R_N$ ПЕРЕРАЗМЕЩАЮТСЯ НА ТОМ ЖЕ МЕСТЕ. пОСЛЕ ЗАВЕРШЕНИЯ СОРТИРОВКИ ИХ 
КЛЮЧИ БУДУТ УПОРЯДОЧЕНЫ: $K_1 \le \ldots \le K_N$. дЛЯ 
УПРАВЛЕНИЯ ПРОЦЕССОМ СОРТИРОВКИ ИСПОЛЬЗУЕТСЯ ВСПОМОГАТЕЛЬНАЯ 
ПОСЛЕДОВАТЕЛЬНОСТЬ ШАГОВ $h_t$, $h_{t-1}$, \dots, $h_1$, ГДЕ $h_1=l$; 
ПРАВИЛЬНО ВЫБРАВ ЭТИ ПРИРАЩЕНИЯ, МОЖНО ЗНАЧИТЕЛЬНО СОКРАТИТЬ ВРЕМЯ 
СОРТИРОВКИ. пРИ $t = 1$ ЭТОТ АЛГОРИТМ СВОДИТСЯ К АЛГОРИТМУ S.

\st[цИКЛ ПО $s$.] вЫПОЛНИТЬ ШАГ \stp{2} ПРИ $s=t$,  $t-1$, \dots, 1,
ПОСЛЕ ЧЕГО ЗАВЕРШИТЬ РАБОТУ АЛГОРИТМА.

\st[цИКЛ ПО $j$.] уСТАНОВИТЬ $h\asg h_s$ И ВЫПОЛНИТЬ ШАГИ \stp{3}, \dots
%% 107
\stp{6} ПРИ $h<j\le N$. (дЛЯ СОРТИРОВКИ ЭЛЕМЕНТОВ, ОТСТОЯЩИХ ДРУГ ОТ 
ДРУГА НА $h$ ПОЗИЦИЙ, ВОСПОЛЬЗУЕМСЯ ПРОСТЫМИ ВСТАВКАМИ И В РЕЗУЛЬТАТЕ 
ПОЛУЧИМ $K_i\le K_{i+h}$ ПРИ $1\le i\le N-h$. шАГИ \stp{3}, \dots, \stp{6},
 ПО СУЩЕСТВУ, ТАКИЕ ЖЕ, КАК СООТВЕТСТВЕННО S2, \dots, S5 В АЛГОРИТМЕ S.) 

\st[уСТАНОВИТЬ $i$, $K$, $R$.] уСТАНОВИТЬ $i\asg j-h$, $K\asg K_j$,
$R\asg R_j$.

\st[сРАВНИТЬ $K$, $K_i$.] еСЛИ $K\ge K_i$, ТО ПЕРЕЙТИ К ШАГУ \stp{6}.

\st[пЕРЕМЕСТИТЬ $R_i$, УМЕНЬШИТЬ $i$.] уСТАНОВИТЬ $R_{i+h}\asg R_i$,
ЗАТЕМ $i\asg i-h$. еСЛИ $i >0$, ТО ВОЗВРАТИТЬСЯ К ШАГУ \stp{4}.

\st[$R$ НА МЕСТО $R_{i+h}$.] уСТАНОВИТЬ $R_{i+h}\asg R$.
\algend

сООТВЕТСТВУЮЩАЯ \MIX-ПРОГРАММА НЕ НАМНОГО ДЛИННЕЕ, ЧЕМ НАША ПРОГРАММА ДЛЯ 
ПРОСТЫХ ВСТАВОК. сТРОКИ 08--19 ЭТОЙ ПРОГРАММЫ ПЕРЕНЕСЕНЫ ИЗ ПРОГРАММЫ S 
В БОЛЕЕ ОБЩИЙ КОНТЕКСТ АЛГОРИТМА D.

\prog D.(сОРТИРОВКА С УБЫВАЮЩИМ ШАГОМ.) пРЕДПОЛАГАЕТСЯ, ЧТО ШАГИ 
СОРТИРОВКИ ХРАНЯТСЯ ВО ВСПОМОГАТЕЛЬНОЙ ТАБЛИЦЕ И $h_s$ НАХОДИТСЯ В ЯЧЕЙКЕ 
$|H|+s$; ВСЕ ШАГИ СОРТИРОВКИ МЕНЬШЕ $N$. сОДЕРЖИМОЕ РЕГИСТРОВ: 
$|rI1|\equiv j-N$; $|rI2|\equiv i$; $|rA|\equiv R \equiv K$; 
$|rI3|\equiv s$; $|rI4|\equiv h$. зАМЕТИМ, ЧТО ЭТА ПРОГРАММА САМА СЕБЯ 
ИЗМЕНЯЕТ. эТО 
СДЕЛАНО ДЛЯ ТОГО, ЧТОБЫ ДОБИТЬСЯ БОЛЕЕ ЭФФЕКТИВНОГО ВЫПОЛНЕНИЯ 
ВНУТРЕННЕГО ЦИКЛА.
\code
START &ENT3 &т        &1        & D1. цИКЛ ПО $s$. $s\asg t$.
1H    &LD4  &H,3      &T        & D2. цИКЛ ПО $j$.$h\asg h_s$.
      &ENT1 &INPUT,4  &т        & иЗМЕНИТЬ АДРЕСА В ТРЕХ
      &ST1  &6F(0:2)  &т        & ИНСТРУКЦИЯХ В
      &ST1  &7F(0:2)  &т        & ОСНОВНОМ ЦИКЛЕ.
      &ENN1 &-N, 4    &т        & $|rIl|\asg N-h$.
      &ST1  &4F(0:2)  &T
      &ENT1 &1-N, 4   &T        & $j\asg h+1$.
2H    &LDA  &INPUT+N,1&NT-S     & D3. уСТАНОВИТЬ $i$, $K$, $R$.
4H    &ENT2 &N-H,1    &NT-S     & $i\asg j-h$. (иЗМЕНЯЕМАЯ ИНСТРУКЦИЯ)
5н    &смра &INPUT,2  &B+NT-S-A & D4. сРАВНИТЬ $K$, $K_i$.
      &JOE  &7F       &B+NT-S-A & к ШАГУ D6, ЕСЛИ $K\ge K_i$.
      &LDX  &INPUT,2  &B        & D5. пЕРЕМЕСТИТЬ  $R_i$, УМЕНЬШИТЬ $i$.
6н    &STX  &INPUT+H,2&в        & $R_{i+h}\asg R_i$. (иЗМЕНЯЕМАЯ ИНСТРУКЦИЯ)
      &DEC2 &0,4      &в        & $i\asg i-h$.
      &J2P  &5в       &в        & к ШАГУ D4, ЕСЛИ $i>0$.
7н    &STA  &INPUT+H,2&NT-S     & D6. $R$ НА МЕСТО $R_{i+h}$. (иЗМЕНЯЕМАЯ ИНСТРУКЦИЯ)
8н    &INC1 &1        &NT-S     & $j\asg j+1$.
      &J1NP &2в       &NT-S     & к D3, ЕСЛИ $j\le N$.
      &DEC3 &1        &т
      &J3P  &1в       &т        & $t\ge s\ge 1$.
\endcode
\progend

%% 108

\section *аНАЛИЗ МЕТОДА шЕЛЛА. чТОБЫ ВЫБРАТЬ ХОРОШУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ 
ШАГОВ СОРТИРОВКИ ДЛЯ АЛГОРИТМА D, НУЖНО ПРОАНАЛИЗИРОВАТЬ ВРЕМЯ РАБОТЫ 
КАК ФУНКЦИЮ ОТ ЭТИХ ШАГОВ. эТО ПРИВОДИТ К ОЧЕНЬ КРАСИВЫМ, НО ЕЩЕ НЕ ДО 
КОНЦА РЕШЕННЫМ МАТЕМАТИЧЕСКИМ ЗАДАЧАМ; НИКОМУ ДО СИХ ПОР НЕ УДАЛОСЬ 
НАЙТИ НАИЛУЧШУЮ ВОЗМОЖНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ ШАГОВ ДЛЯ БОЛЬШИХ $N$. тЕМ 
НЕ МЕНЕЕ ИЗВЕСТНО ДОВОЛЬНО МНОГО ИНТЕРЕСНЫХ ФАКТОВ О ПОВЕДЕНИИ СОРТИРОВКИ 
МЕТОДОМ шЕЛЛА С УБЫВАЮЩИМ ШАГОМ, И МЫ ЗДЕСЬ ИХ КРАТКО ИЗЛОЖИМ; ПОДРОБНОСТИ 
МОЖНО НАЙТИ В ПРИВЕДЕННЫХ НИЖЕ УПРАЖНЕНИЯХ. [чИТАТЕЛЯМ, НЕ ИМЕЮЩИМ 
СКЛОННОСТИ К МАТЕМАТИКЕ, ЛУЧШЕ ПРОПУСТИТЬ СЛЕДУЮЩИЕ НЕСКОЛЬКО СТРАНИЦ, 
ДО ФОРМУЛ (8).]

сЧЕТЧИКИ ЧАСТОТ ВЫПОЛНЕНИЯ В ПРОГРАММЕ D ПОКАЗЫВАЮТ, ЧТО НА ВРЕМЯ 
ВЫПОЛНЕНИЯ ВЛИЯЮТ ПЯТЬ ФАКТОРОВ: РАЗМЕР ФАЙЛА $N$, ЧИСЛО ПРОСМОТРОВ (Т.Е. 
ЧИСЛО ШАГОВ) $T=t$, СУММА ШАГОВ
$$
S=h_1+\cdots+h_t,
$$
ЧИСЛО СРАВНЕНИЙ $B+NT-S-A$ И ЧИСЛО ПЕРЕМЕЩЕНИЙ $B$. кАК И ПРИ АНАЛИЗЕ 
ПРОГРАММЫ S, ЗДЕСЬ $A$ РАВНО ЧИСЛУ ЛЕВОСТОРОННИХ МИНИМУМОВ, 
ВСТРЕЧАЮЩИХСЯ ПРИ ПРОМЕЖУТОЧНЫХ ОПЕРАЦИЯХ СОРТИРОВКИ, А $B$ РАВНО ЧИСЛУ 
ИНВЕРСИЙ В ПОДФАЙЛАХ. оСНОВНЫМ ФАКТОРОМ, ОТ КОТОРОГО ЗАВИСИТ ВРЕМЯ РАБОТЫ, 
ЯВЛЯЕТСЯ ВЕЛИЧИНА $B$, ПОЭТОМУ НА НЕЕ МЫ И ОБРАТИМ ГЛАВНЫМ ОБРАЗОМ СВОЕ 
ВНИМАНИЕ. пРИ АНАЛИЗЕ БУДЕТ ПРЕДПОЛАГАТЬСЯ, ЧТО КЛЮЧИ РАЗЛИЧНЫ И 
ПЕРВОНАЧАЛЬНО РАСПОЛОЖЕНЫ В СЛУЧАЙНОМ ПОРЯДКЕ.

нАЗОВЕМ ОПЕРАЦИЮ ШАГА D2 "$h$-СОРТИРОВКОЙ". тОГДА СОРТИРОВКА МЕТОДОМ 
шЕЛЛА СОСТОИТ ИЗ $h_t$-СОРТИРОВКИ, ЗА КОТОРОЙ СЛЕДУЕТ $h_{t-1}$-СОРТИРОВКА,
 \dots, ЗА КОТОРОЙ СЛЕДУЕТ $h_1$-СОРТИРОВКА. фАЙЛ, В КОТОРОМ $K_i\le 
K_{i+h}$ ПРИ $1\le i \le N-h$, БУДЕМ НАЗЫВАТЬ  $h\hbox{-УПОРЯДОЧЕННЫМ}$.

рАССМОТРИМ СНАЧАЛА ПРОСТЕЙШЕЕ ОБОБЩЕНИЕ ПРОСТЫХ ВСТАВОК, КОГДА ИМЕЮТСЯ 
ВСЕГО ДВА ШАГА $h_2=2$ И $h_1=1$. вО ВРЕМЯ ВТОРОГО ПРОСМОТРА ИМЕЕМ 
2-УПОРЯДОЧЕННУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ КЛЮЧЕЙ $K_1$ $K_2$ \dots $K_N$. лЕГКО 
ВИДЕТЬ, ЧТО ЧИСЛО ПЕРЕСТАНОВОК $a_1$ $a_2$~\dots $a_n$ МНОЖЕСТВА $\{1, 2, 
\ldots, П\}$, ТАКИХ, ЧТО $a_i\le a_{i+2}$ ПРИ $l\le i \le n-2$, РАВНО
$$
\perm{n}{\floor{n/2}},
$$
ТАК КАК СУЩЕСТВУЕТ ВСЕГО ОДНА 2-УПОРЯДОЧЕННАЯ ПЕРЕСТАНОВКА ДЛЯ КАЖДОГО 
ВЫБОРА $\floor{n/2}$ ЭЛЕМЕНТОВ, РАСПОЛОЖЕННЫХ В ЧЕТНЫХ ПОЗИЦИЯХ $a_2a_4$, 
\dots, ТОГДА ОСТАЛЬНЫЕ $\ceil{n/2}$ ЭЛЕМЕНТОВ ПОПАДАЮТ В ПОЗИЦИИ С 
НЕЧЕТНЫМИ НОМЕРАМИ. пОСЛЕ 2-СОРТИРОВКИ СЛУЧАЙНОГО ФАЙЛА С ОДИНАКОВОЙ 
ВЕРОЯТНОСТЬЮ МОЖЕТ ПОЛУЧИТЬСЯ ЛЮБАЯ 2-УПОРЯДОЧЕННАЯ ПЕРЕСТАНОВКА. кАКОВО 
СРЕДНЕЕ ЧИСЛО ИНВЕРСИЙ ВО ВСЕХ ТАКИХ ПЕРЕСТАНОВКАХ?
%% 109
\bye