\input style
%% 118
ПРИБЛИЖЕНИЕМ ПРИ $100\le N\le 60\ 000$ СЛУЖАТ СЛЕДУЮЩИЕ ФОРМУЛЫ:
$$
\displaylines{
\hbox{$1.09N^{1.27}$ ИЛИ $.30N(\ln N)^2-1.35N\ln N$ ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ 
ШАГОВ $2^k+1$,\dots, 9, 5, 3, 1;}\hfill\cr
\hbox{$1.22N^{1.26}$ ИЛИ $.29N(\ln N)^2-1.26N\ln N$ ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ 
ШАГОВ $2^k-1$, \dots, 15, 7, 3, 1;}\hfill\cr
\hbox{$1.12N^{1.28}$ ИЛИ $.36N(\ln N)^2- 1.73N \ln N$ ДЛЯ 
ПОСЛЕДОВАТЕЛЬНОСТИ ШАГОВ $(2^k\pm 1)/3$, \dots, 11, 5, 3, 1;}\hfill\cr
\hbox{$1.66N^{1.25}$ ИЛИ $.33N(\ln N)^2-1.26N\ln N$ ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ 
ШАГОВ $(3^k-1)/2$, \dots, 40, 13, 4, 1.}\hfill\cr
}
$$
нАПРИМЕР, ПРИ $N=20\ 000$ ДЛЯ ВСЕХ ЭТИХ ТИПОВ ШАГОВ 
ПОЛУЧАЕМ СООТВЕТСТВЕННО $B\approx 31\ 000$, $33\ 000$, $35\ 000$, 
$39\ 000$. тАБЛ.~7 ДАЕТ
\htable{тАБЛИЦА 7}%
{кОЛИЧЕСТВА ПЕРЕМЕЩЕНИЙ ПО ПРОСМОТРАМ (ПРИМЕРЫ ДЛЯ  $N=20 000$)}%
{\bskip\hfill$#$\bskip\hfill&\bskip\hfill$#$\bskip\bskip\hfill&\bskip\hfill$#$\bskip\hfill&\bskip\hfill$#$\bskip\bskip\hfill&\bskip\hfill$#$\bskip\hfill&\bskip\hfill$#$\bskip\bskip\hfill\cr
h_s & B_s & h_s & B_s & h_s & B_s \cr
\noalign{\hrule}
4095 & 19460 & 4097 & 19550 & 3280 & 25210\cr
2047 & 15115 & 2049 & 14944 & 1093 & 28324\cr
1023 & 15869 & 1025 & 15731 &  364 & 35477\cr
 511 & 18891 &  513 & 18548 &  121 & 47158\cr
 255 & 22306 &  257 & 21827 &   40 & 62110\cr
 127 & 27400 &  129 & 27814 &   13 & 88524\cr
  63 & 35053 &   65 & 33751 &    4 & 74599\cr
  31 & 34677 &   33 & 34303 &    1 & 34666\cr
  15 & 51054 &   17 & 46044\cr
   7 & 40382 &    9 & 35817\cr
   3 & 24044 &    5 & 19961\cr
   1 & 16789 &    3 &  9628\cr
     &       &    1 & 13277\cr
\noalign{\hrule}
}
ТИПИЧНУЮ КАРТИНУ ТОГО, КАК РАСПРЕДЕЛЯЮТСЯ ПЕРЕМЕЩЕНИЯ ПО ПРОСМОТРАМ В ТРЕХ 
ИЗ ЭТИХ ЭКСПЕРИМЕНТОВ. лЮБОПЫТНО, ЧТО \emph{ОБА} ВИДА ФУНКЦИЙ $\alpha N 
(\ln N)^2+\beta N\ln N$ И $\beta N^\alpha$, КАЖЕТСЯ, ДОВОЛЬНО ХОРОШО 
СОГЛАСУЮТСЯ С НАБЛЮДАЕМЫМИ ДАННЫМИ, ХОТЯ СТЕПЕННАЯ ФУНКЦИЯ БЫЛА 
СУЩЕСТВЕННО ЛУЧШЕ ПРИ МЕНЬШИХ ЗНАЧЕНИЯХ $N$. дАЛЬНЕЙШИЕ ЭКСПЕРИМЕНТЫ БЫЛИ 
ВЫПОЛНЕНЫ ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ ШАГОВ $2^k-1$ СО ЗНАЧЕНИЕМ $N$, 
ДОСТИГАЮЩИМ $250\ 000$; СОРОК ПЯТЬ ИСПЫТАНИЙ С $N = 250\ 000$ ДАЛИ 
ЗНАЧЕНИЕ $B\approx 7\ 900\ 000$ ПРИ НАБЛЮДАЕМОМ СТАНДАРТНОМ ОТКЛОНЕНИИ 
$50\ 000$. "нАИБОЛЕЕ ПОДХОДЯЩИМИ" ФОРМУЛАМИ ДЛЯ ДИАПАЗОНА $100 \le N \le 
250\ 000$ ОКАЗАЛИСЬ СООТВЕТСТВЕННО $1.21N^{1.26}$ И~$.39N (\ln N)^2- 2.33 
N \ln N$. тАК КАК
%%119
КОЭФФИЦИЕНТЫ В ПРЕДСТАВЛЕНИИ СТЕПЕННОЙ ФУНКЦИЕЙ ОСТАЛИСЬ ПОЧТИ ТАКИМИ ЖЕ, 
В ТО ВРЕМЯ КАК КОЭФФИЦИЕНТЫ В ЛОГАРИФМИЧЕСКОМ ПРЕДСТАВЛЕНИИ ДОВОЛЬНО 
РЕЗКО ИЗМЕНИЛИСЬ, ТО РАЗУМНО ПРЕДПОЛОЖИТЬ, ЧТО ИМЕННО СТЕПЕННАЯ ФУНКЦИЯ 
ОПИСЫВАЕТ ИСТИННОЕ АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ МЕТОДА шЕЛЛА.

эТИ ЭМПИРИЧЕСКИЕ ДАННЫЕ НИ КОИМ ОБРАЗОМ НЕ ИСЧЕРПЫВАЮТ ВСЕХ ВОЗМОЖНОСТЕЙ, 
И МЫ НЕ ПОЛУЧИЛИ ОСНОВАНИЙ ДЛЯ РЕШИТЕЛЬНЫХ ЗАКЛЮЧЕНИЙ О ТОМ, КАКИЕ ЖЕ 
ПОСЛЕДОВАТЕЛЬНОСТИ ШАГОВ ЯВЛЯЮТСЯ НАИЛУЧШИМИ ДЛЯ АЛГОРИТМА D. пОСКОЛЬКУ 
ПРИРАЩЕНИЯ ВИДА $(3^k-1)/2$ НЕ УВЕЛИЧИВАЮТ СУЩЕСТВЕННО ЧИСЛА 
ПЕРЕМЕЩЕНИЙ И ПОСКОЛЬКУ ДЛЯ НИХ ТРЕБУЕТСЯ ЛИШЬ ПРИМЕРНО 5/8 ЧИСЛА 
ПРОСМОТРОВ, НЕОБХОДИМЫХ ДЛЯ ШАГОВ ДРУГИХ ТИПОВ, ТО, ОЧЕВИДНО,
 \emph{РАЗУМНО ВЫБИРАТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ ШАГОВ СЛЕДУЮЩИМ ОБРАЗОМ:}
$$
\hbox{\it пРИНЯТЬ $h_t=1$, $h_{s+1}=3h_s+1$ И ОСТАНОВИТЬСЯ НА $h_t$, КОГДА 
$h_{t+2}\ge N$.}
\eqno (8)
$$

\section вСТАВКИ В СПИСОК. оСТАВИМ ТЕПЕРЬ МЕТОД шЕЛЛА И РАССМОТРИМ ДРУГИЕ 
ПУТИ УСОВЕРШЕНСТВОВАНИЯ ПРОСТЫХ ВСТАВОК. сРЕДИ ОБЩИХ СПОСОБОВ УЛУЧШЕНИЯ 
АЛГОРИТМА ОДИН ИЗ САМЫХ ВАЖНЫХ ОСНОВЫВАЕТСЯ НА ТЩАТЕЛЬНОМ АНАЛИЗЕ 
СТРУКТУР ДАННЫХ, ПОСКОЛЬКУ РЕОРГАНИЗАЦИЯ СТРУКТУР ДАННЫХ, ПОЗВОЛЯЮЩАЯ 
ИЗБЕЖАТЬ НЕНУЖНЫХ ОПЕРАЦИЙ, ЧАСТО ДАЕТ СУЩЕСТВЕННЫЙ ЭФФЕКТ. дАЛЬНЕЙШЕЕ 
ОБСУЖДЕНИЕ ЭТОЙ ОБЩЕЙ ИДЕИ МОЖНО НАЙТИ В \S~2.4, В КОТОРОМ 
ИЗУЧАЕТСЯ ДОВОЛЬНО СЛОЖНЫЙ АЛГОРИТМ. пОСМОТРИМ, КАК ОНА ПРИМЕНЯЕТСЯ К 
ТАКОМУ НЕХИТРОМУ АЛГОРИТМУ, КАК ПРОСТЫЕ ВСТАВКИ. кАКОВА НАИБОЛЕЕ 
ПОДХОДЯЩАЯ СТРУКТУРА ДАННЫХ ДЛЯ АЛГОРИТМА S?

сОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ СОСТОИТ ИЗ ДВУХ ОСНОВНЫХ ОПЕРАЦИЙ:
\medskip
\item{i)} ПРОСМОТРА УПОРЯДОЧЕННОГО ФАЙЛА ДЛЯ НАХОЖДЕНИЯ НАИБОЛЬШЕГО 
КЛЮЧА, МЕНЬШЕГО ИЛИ РАВНОГО ДАННОМУ КЛЮЧУ;

\item{ii)} ВСТАВКИ НОВОЙ ЗАПИСИ В ОПРЕДЕЛЕННОЕ МЕСТО УПОРЯДОЧЕННОГО ФАЙЛА.
\medskip
\noindent фАЙЛ---ЭТО, ОЧЕВИДНО, ЛИНЕЙНЫЙ СПИСОК, И АЛГОРИТМ S ОБРАБАТЫВАЕТ 
ЕГО, ИСПОЛЬЗУЯ ПОСЛЕДОВАТЕЛЬНОЕ РАСПРЕДЕЛЕНИЕ (П.~2.2.2);
ПОЭТОМУ ДЛЯ ВЫПОЛНЕНИЯ КАЖДОЙ ОПЕРАЦИИ ВСТАВКИ НЕОБХОДИМО ПЕРЕМЕСТИТЬ 
ПРИМЕРНО ПОЛОВИНУ ЗАПИСЕЙ. с ДРУГОЙ СТОРОНЫ, НАМ ИЗВЕСТНО, ЧТО ДЛЯ ВСТАВОК 
ИДЕАЛЬНО ПОДХОДИТ СВЯЗАННОЕ РАСПРЕДЕЛЕНИЕ (П.~2.2.3), ТАК КАК ПРИ ЭТОМ 
ТРЕБУЕТСЯ ИЗМЕНИТЬ ЛИШЬ НЕСКОЛЬКО СВЯЗЕЙ; ДРУГАЯ ОПЕРАЦИЯ---ПОСЛЕДОВАТЕЛЬНЫЙ 
ПРОСМОТР---ПРИ СВЯЗАННОМ РАСПРЕДЕЛЕНИИ ПОЧТИ ТАК ЖЕ ПРОСТА, КАК И ПРИ 
ПОСЛЕДОВАТЕЛЬНОМ. пОСКОЛЬКУ СПИСКИ ВСЕГДА ПРОСМАТРИВАЮТСЯ В ОДНОМ И ТОМ 
ЖЕ НАПРАВЛЕНИИ, ТО ДОСТАТОЧНО ИМЕТЬ СПИСКИ С ОДНОЙ СВЯЗЬЮ. тАКИМ ОБРАЗОМ, 
ПРИХОДИМ К ВЫВОДУ, ЧТО "ПРАВИЛЬНАЯ" СТРУКТУРА ДАННЫХ ДЛЯ МЕТОДА ПРОСТЫХ 
ВСТАВОК---ЛИНЕЙНЫЕ
%% 120
СПИСКИ С ОДНОЙ СВЯЗЬЮ. уДОБНО ТАКЖЕ ИЗМЕНИТЬ АЛГОРИТМ S, 
ЧТОБЫ СПИСОК ПРОСМАТРИВАЛСЯ В  ВОЗРАСТАЮЩЕМ ПОРЯДКЕ.

\alg L.(вСТАВКИ В СПИСОК.) пРЕДПОЛАГАЕТСЯ, ЧТО ЗАПИСИ $R_1$,\dots, $R_N$ 
СОДЕРЖАТ КЛЮЧИ $K_1$, \dots, $K_N$ И~"ПОЛЯ СВЯЗИ" $L_1$, \dots, $L_N$, В 
КОТОРЫХ МОГУТ ХРАНИТЬСЯ ЧИСЛА ОТ~0 ДО~$N$;
ИМЕЕТСЯ ТАКЖЕ ЕЩЕ ОДНО ПОЛЕ СВЯЗИ $L_0$ В НЕКОТОРОЙ ИСКУССТВЕННОЙ ЗАПИСИ 
$R_0$ В НАЧАЛЕ ФАЙЛА. аЛГОРИТМ УСТАНАВЛИВАЕТ ПОЛЯ СВЯЗИ ТАК, ЧТО ЗАПИСИ 
ОКАЗЫВАЮТСЯ СВЯЗАННЫМИ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ. тАК, ЕСЛИ $p(1) \ldots 
p(N)$---"УСТОЙЧИВАЯ" ПЕРЕСТАНОВКА, ТАКАЯ, ЧТО 
$K_{p(1)}\le \ldots \le K_{p(N)}$, ТО В РЕЗУЛЬТАТЕ ПРИМЕНЕНИЯ АЛГОРИТМА 
ПОЛУЧИМ
$$
L_0=p(1); L_{p(i)}=p(i+1)\ \hbox{ПРИ $1\le i<N$}; L_{p(N)}=0. 
\eqno(9)
$$
\st[цИКЛ ПО $j$.] уСТАНОВИТЬ $L_0\asg N$, $L_N\asg0$. ($L_0$ 
СЛУЖИТ "ГОЛОВОЙ" СПИСКА, А 0---ПУСТОЙ СВЯЗЬЮ; СЛЕДОВАТЕЛЬНО, СПИСОК, ПО 
СУЩЕСТВУ, ЦИКЛИЧЕСКИЙ.) вЫПОЛНИТЬ ШАГИ ОТ \stp{2} ДО \stp{5} ПРИ $j=N-1$, 
$N-2$, \dots, $1$ И ЗАВЕРШИТЬ РАБОТУ АЛГОРИТМА.

\st[уСТАНОВИТЬ $p$, $q$, $K$.] уСТАНОВИТЬ $p\asg L_0$,  $q\asg0$, 
$K\asg K_j$. (в ПОСЛЕДУЮЩИХ ШАГАХ МЫ ВСТАВИМ ЗАПИСЬ $R_j$ В НУЖНОЕ МЕСТО В 
СВЯЗАННОМ СПИСКЕ ПУТЕМ СРАВНЕНИЯ КЛЮЧА $K$ С ПРЕДЫДУЩИМИ КЛЮЧАМИ В 
ВОЗРАСТАЮЩЕМ ПОРЯДКЕ. пЕРЕМЕННЫЕ $p$ И~$q$ СЛУЖАТ УКАЗАТЕЛЯМИ НА ТЕКУЩЕЕ 
МЕСТО В СПИСКЕ, ПРИЧЕМ $p=L_q$, ТАК ЧТО $q$ ВСЕГДА НА ОДИН ШАГ ОТСТАЕТ 
ОТ $p$.)

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

\st[пРОДВИНУТЬ $p$, $q$.] уСТАНОВИТЬ $q\asg p$, $p\asg L_q$. еСЛИ $p>0$,
 ТО ВОЗВРАТИТЬСЯ К ШАГУ \stp{3}. (еСЛИ $p=0$, ТО $K$---НАИБОЛЬШИЙ КЛЮЧ, 
ОБНАРУЖЕННЫЙ ДО СИХ ПОР; СЛЕДОВАТЕЛЬНО, ЗАПИСЬ $R$ ДОЛЖНА ПОПАСТЬ В 
КОНЕЦ СПИСКА, МЕЖДУ $R_q$ И $R_0$.)

\st[вСТАВИТЬ В СПИСОК.] уСТАНОВИТЬ $L_q\asg j$, $L_j\asg p$. 
\algend

\ctable{
\strut\bskip\hfill$#:$\hfill\bskip&&\bskip\hfill#\hfill\bskip\cr
\noalign{\rightline{\it тАБЛИЦА 8}}
\noalign{\centerline{\bf пРИМЕР ПРИМЕНЕНИЯ АЛГОРИТМА ВСТАВОК В СПИСОК}}
\noalign{\hrule}
  j&  0&  1&  2&  3&  4&  5&  6&  7&  8&  9& 10& 11& 12& 13& 14& 15& 16\cr
K_i&---&503&087&512&061&908&170&897&275&653&426&154&509&612&677&765&703\cr
L_j& 16&---&---&---&---&---&---&---&---&---&---&---&---&---&---&---&  0\cr
L_j& 16&---&---&---&---&---&---&---&---&---&---&---&---&---&---&  0& 15\cr
L_j& 14&---&---&---&---&---&---&---&---&---&---&---&---&---& 16&  0& 15\cr
\noalign{\hrule}
}
%% 121
\bye