\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