\input style

эТОТ АЛГОРИТМ ВАЖЕН НЕ ТОЛЬКО КАК ПРОСТОЙ МЕТОД СОРТИРОВКИ, НО И ПОТОМУ, 
ЧТО ОН ЧАСТО ВСТРЕЧАЕТСЯ КАК ЧАСТЬ ДРУГИХ АЛГОРИТМОВ ОБРАБОТКИ СПИСКОВ. в 
ТАБЛ.~8 ПОКАЗАНЫ ПЕРВЫЕ НЕСКОЛЬКО ШАГОВ СОРТИРОВКИ ШЕСТНАДЦАТИ ЧИСЕЛ, 
ВЫБРАННЫХ НАМИ ДЛЯ ПРИМЕРОВ.

\prog L.(вСТАВКИ В СПИСОК.) пРЕДПОЛАГАЕТСЯ, ЧТО КЛЮЧ~$K_j$ ХРАНИТСЯ В 
ПОЛЕ~$|INPUT|+j(0:3)$,  a~$L_j$---В ПОЛЕ~$|INPUT|+j(4:5)$. зНАЧЕНИЯ 
РЕГИСТРОВ: $|rI1|\equiv j$; $|rI2|\equiv p$; $|rI3|\equiv =q$; 
$|rA|(0:3)\equiv K$. 
\code
KEY  &EQU  & 0:3
LINK &EQU  & 4:5
START&ENT1 & N            & 1      & L1. цИКЛ ПО~$j$, $j\asg N$.
     &ST1  & INPUT(LINK)  & 1      & $L_0\asg N$.
     &STZ  & INPUT+N(LINK)& 1      & $L_N\asg 0$.
     &JMP  & 6F           & 1      & пЕРЕХОД К УМЕНЬШЕНИЮ~$j$.
2H   &LD2  & INPUT(LINK)  & N-1    & L2. уСТАНОВИТЬ~$p$, $q$, $K$. $p\asg L_0$.
     &ENT3 & 0            & N-1    & $q\asg 0$.
     &LDA  & INPUT,1      & N-1    & $K\asg K_j$.
3H   &CMPA & INPUT,2(KEY) & B+N-1-A& L3. сРАВНИТЬ~$K$, $K_p$.
     &JLE  & 5F           & B+N-1-A& K~L5, ЕСЛИ~$K\le K_p$.
4H   &ENT3 & 0,2          & B      & L4. пРОДВИНУТЬ~$p$, $q$. $q\asg p$. 
     &LD2  & INPUT,3(LINK)& B      & $p\asg L_q$.
     &J2P  & 3в           & B      & к L3, ЕСЛИ~$p>0$.
5H   &ST1  & INPUT,3(LINK)& N-1    & L5. вСТАВИТЬ В СПИСОК. $L_q\asg j$.
     &ST2  & INPUT,1(LINK)& N-1    & $L_j\asg p$.
6H   &DEC1 & 1            & N
     &J1P  & 2в           & N      & $N>j \ge 1$.
\endcode
\progend

вРЕМЯ РАБОТЫ ЭТОЙ ПРОГРАММЫ РАВНО $7B+14N-3A-6$~ЕДИНИЦ, ГДЕ~$N$---ДЛИНА 
ФАЙЛА, $A$---ЧИСЛО ПРАВОСТОРОННИХ МАКСИМУМОВ, А~$B$---ЧИСЛО ИНВЕРСИЙ В 
ИСХОДНОЙ ПЕРЕСТАНОВКЕ. (сР. С АНАЛИЗОМ ПРОГРАММЫ~S. зАМЕТЬТЕ, ЧТО 
ПРОГРАММА~L НЕ ПЕРЕМЕЩАЕТ ЗАПИСИ В ПАМЯТИ; ЭТО МОЖНО СДЕЛАТЬ, КАК В 
УПР.~5.2-12, ЗАТРАТИВ ДОПОЛНИТЕЛЬНО $20N$~ЕДИНИЦ ВРЕМЕНИ.) пРОГРАММА~S 
ТРЕБУЕТ $(9B+10N-3A-9)u$, А ТАК КАК $B$~РАВНО ПРИМЕРНО~${1\over 4}N^2$, ТО
НЕТРУДНО ВИДЕТЬ, ЧТО ЗА СЧЕТ ДОПОЛНИТЕЛЬНОГО ПРОСТРАНСТВА ПАМЯТИ, 
ВЫДЕЛЕННОГО ПОД ПОЛЯ СВЯЗИ, УДАЛОСЬ СЭКОНОМИТЬ ПРИМЕРНО 22\% ВРЕМЕНИ 
РАБОТЫ. аККУРАТНО ПРОГРАММИРУЯ, МОЖНО СБЕРЕЧЬ ЕЩЕ 22\% (СМ.~УПР.~33), НО 
ВРЕМЯ РАБОТЫ ВСЕ ЖЕ ОСТАНЕТСЯ ПРОПОРЦИОНАЛЬНЫМ~$N^2$.

\emph{пОДВЕДЕМ ИТОГ СДЕЛАННОМУ ДО СИХ ПОР.} мЫ НАЧАЛИ С 
АЛГОРИТМА~S---ПРОСТОГО И ЕСТЕСТВЕННОГО АЛГОРИТМА СОРТИРОВКИ, КОТОРЫЙ
%%122
ВЫПОЛНЯЕТ ОКОЛО ${1\over4}N^2$ СРАВНЕНИЙ И ОКОЛО ${1\over4}N^2$ 
ПЕРЕМЕЩЕНИЙ. мЫ УСОВЕРШЕНСТВОВАЛИ ЕГО, РАССМОТРЕВ БИНАРНЫЕ ВСТАВКИ, ПРИ 
КОТОРЫХ ВЫПОЛНЯЕТСЯ ОКОЛО $N\log_2N$ СРАВНЕНИЙ И ${1\over4}N^2$
ПЕРЕМЕЩЕНИЙ. нЕСКОЛЬКО ИЗМЕНИВ СТРУКТУРУ ДАННЫХ, ПРИМЕНИВ "ДВУХПУТЕВЫЕ 
ВСТАВКИ", СУМЕЛИ СОКРАТИТЬ ЧИСЛО ПЕРЕМЕЩЕНИЙ
ДО ${1\over8}N^2$. пРИ СОРТИРОВКЕ МЕТОДОМ шЕЛЛА "С УБЫВАЮЩИМ ШАГОМ"
ЧИСЛО СРАВНЕНИЙ И ПЕРЕМЕЩЕНИЙ СНИЖАЕТСЯ ПРИМЕРНО ДО $N^{1.3}$ ДЛЯ ТЕХ 
ЗНАЧЕНИЙ $N$, КОТОРЫЕ ВСТРЕЧАЮТСЯ НА ПРАКТИКЕ; ПРИ $N\to\infty$ ЭТО ЧИСЛО 
МОЖНО СОКРАТИТЬ ДО ПОРЯДКА $N(\log_2N)^2$. дАЛЬНЕЙШЕЕ СТРЕМЛЕНИЕ УЛУЧШИТЬ 
АЛГОРИТМ---ПУТЕМ ПРИМЕНЕНИЯ СВЯЗАННОЙ СТРУКТУРЫ ДАННЫХ---ПРИВЕЛО НАС К 
ВСТАВКАМ В СПИСОК,
ПРИ КОТОРЫХ ВЫПОЛНЯЕТСЯ ОКОЛО ${1\over4}N^2$ СРАВНЕНИЙ, 0 ПЕРЕМЕЩЕНИЙ
И $2N$ ИЗМЕНЕНИЙ СВЯЗЕЙ.

мОЖНО ЛИ СОЕДИНИТЬ ЛУЧШИЕ СВОЙСТВА ЭТИХ МЕТОДОВ, СОКРАТИВ ЧИСЛО СРАВНЕНИЙ 
ДО ПОРЯДКА $N\log N$, КАК ПРИ БИНАРНЫХ ВСТАВКАХ, И ИСКЛЮЧИВ ПРИ ЭТОМ 
ПЕРЕМЕЩЕНИЯ ДАННЫХ, КАК ПРИ ВСТАВКАХ
\picture{рИС. 13. пРИМЕР СХЕМЫ уИЛЕРА ДЛЯ ВСТАВОК В ДЕРЕВО.}
В СПИСОК? оТВЕТ УТВЕРДИТЕЛЬНЫЙ: ЭТО ДОСТИГАЕТСЯ ПЕРЕХОДОМ К ДРЕВОВИДНОЙ 
СТРУКТУРЕ. тАКАЯ ВОЗМОЖНОСТЬ БЫЛА ВПЕРВЫЕ ИССЛЕДОВАНА ОКОЛО 1957~Г. 
д.~дЖ.~уИЛЕРОМ, КОТОРЫЙ ПРЕДЛОЖИЛ ИСПОЛЬЗОВАТЬ ДВУХПУТЕВЫЕ ВСТАВКИ ДО ТЕХ 
ПОР, ПОКА НЕ ПОЯВИТСЯ НЕОБХОДИМОСТЬ ПЕРЕМЕЩАТЬ ДАННЫЕ. тОГДА ВМЕСТО ТОГО, 
ЧТОБЫ ИХ ПЕРЕМЕЩАТЬ, ВСТАВЛЯЕТСЯ УКАЗАТЕЛЬ НА НОВУЮ ОБЛАСТЬ ПАМЯТИ, И ТОТ 
ЖЕ САМЫЙ МЕТОД РЕКУРРЕНТНО ПРИМЕНЯЕТСЯ КО ВСЕМ ЭЛЕМЕНТАМ, КОТОРЫЕ НУЖНО 
ВСТАВИТЬ В ЭТУ НОВУЮ ОБЛАСТЬ ПАМЯТИ. оРИГИНАЛЬНЫЙ МЕТОД уИЛЕРА 
[СМ. A. S. Douglas, {\sl Comp. J.,\/} {\bf 2} (1959), 5] ПРЕДСТАВЛЯЕТ 
СОБОЙ СЛОЖНУЮ КОМБИНАЦИЮ ПОСЛЕДОВАТЕЛЬНОЙ И СВЯЗАННОЙ ПАМЯТИ С УЗЛАМИ 
ПЕРЕМЕННОГО РАЗМЕРА; ДЛЯ НАШИХ ШЕСТНАДЦАТИ ЧИСЕЛ БЫЛО БЫ СФОРМИРОВАНО 
ДЕРЕВО, ПОКАЗАННОЕ НА РИС.~13. аНАЛОГИЧНУЮ, НО БОЛЕЕ ПРОСТУЮ СХЕМУ 
ВСТАВКИ В ДЕРЕВО С ИСПОЛЬЗОВАНИЕМ БИНАРНЫХ ДЕРЕВЬЕВ НЕЗАВИСИМО 
%% 123
РАЗРАБОТАЛ ОКОЛО 1958~Г. к.м.~бЕРНЕС-лИ 
[СМ. {\sl Comp. J.\/}, {\bf 3} (1960), 174, 184]. 
сАМ ЭТОТ МЕТОД И ЕГО МОДЕРНИЗАЦИИ ВЕСЬМА ВАЖНЫ КАК ДЛЯ СОРТИРОВКИ, ТАК И 
ДЛЯ ПОИСКА, ПОЭТОМУ ПОДРОБНО ОНИ ОБСУЖДАЮТСЯ В ГЛ.~ 6.

еЩЕ ОДИН ПУТЬ УЛУЧШИТЬ ПРОСТЫЕ ВСТАВКИ---ПОПЫТАТЬСЯ ВСТАВЛЯТЬ НЕСКОЛЬКО 
ЭЛЕМЕНТОВ ОДНОВРЕМЕННО. еСЛИ, НАПРИМЕР, ИМЕЕТСЯ ФАЙЛ ИЗ 1000 ЭЛЕМЕНТОВ И 
998 ИЗ НИХ УЖЕ ОТСОРТИРОВАНЫ, ТО АЛГОРИТМ S ВЫПОЛНИТ ЕЩЕ ДВА ПРОСМОТРА 
ФАЙЛА (ВСТАВИВ СНАЧАЛА $R_{999}$, А ПОТОМ $R_{1000}$). оЧЕВИДНО, МОЖНО 
СЭКОНОМИТЬ ВРЕМЯ, ЕСЛИ СНАЧАЛА СРАВНИТЬ КЛЮЧИ $K_{999}$ c $K_{1000}$ ЧТОБЫ 
ВЫЯСНИТЬ, КОТОРЫЙ ИЗ НИХ БОЛЬШЕ, А ПОТОМ ВСТАВИТЬ ИХ \emph{ОБА} ЗА ОДИН 
ПРОСМОТР ФАЙЛА. кОМБИНИРОВАННАЯ ОПЕРАЦИЯ ТАКОГО РОДА ТРЕБУЕТ ОКОЛО 
$(2/3)N$ СРАВНЕНИЙ И ПЕРЕМЕЩЕНИЙ (СР. С УПР.~3.4.2--5) ВМЕСТО ДВУХ 
ПРОСМОТРОВ, ПРИМЕРНО ПО $N/2$ СРАВНЕНИЙ И ПЕРЕМЕЩЕНИЙ КАЖДЫЙ.

иНАЧЕ ГОВОРЯ, ОБЫЧНО БЫВАЕТ ПОЛЕЗНО "ГРУППИРОВАТЬ" ОПЕРАЦИИ, КОТОРЫЕ 
ТРЕБУЮТ ДЛИТЕЛЬНОГО ПОИСКА, ЧТОБЫ МОЖНО БЫЛО ВЫПОЛНИТЬ НЕСКОЛЬКО ОПЕРАЦИЙ 
ВМЕСТЕ. еСЛИ ДОВЕСТИ ЭТУ ИДЕЮ ДО ЕЕ ЕСТЕСТВЕННОГО ЗАВЕРШЕНИЯ, ТО МЫ ЗАНОВО 
ОТКРОЕМ ДЛЯ СЕБЯ СОРТИРОВКУ ПОСРЕДСТВОМ СЛИЯНИЯ, НАСТОЛЬКО ВАЖНУЮ, ЧТО 
ЕЙ ПОСВЯЩЕН ОТДЕЛЬНЫЙ ПУНКТ.

\section сОРТИРОВКА С ВЫЧИСЛЕНИЕМ АДРЕСА. тЕПЕРЬ УЖ МЫ, НЕСОМНЕННО,
 ИСЧЕРПАЛИ ВСЕ ВОЗМОЖНЫЕ СПОСОБЫ УСОВЕРШЕНСТВОВАТЬ МЕТОД ПРОСТЫХ ВСТАВОК, 
НО ДАВАЙТЕ ПОДУМАЕМ ЕЩЕ! пРЕДСТАВЬТЕ СЕБЕ, ЧТО ВАМ ДАЛИ ЧИСТЫЙ ЛИСТ БУМАГИ 
И СОБИРАЮТСЯ ДИКТОВАТЬ КАКИЕ-ТО СЛОВА. вАША ЗАДАЧА---ЗАПИСАТЬ ИХ В 
АЛФАВИТНОМ ПОРЯДКЕ И ВЕРНУТЬ ЛИСТОК С ОТСОРТИРОВАННЫМ СПИСКОМ СЛОВ. 
уСЛЫШАВ СЛОВО НА БУКВУ а, ВЫ БУДЕТЕ СТРЕМИТЬСЯ ЗАПИСАТЬ ЕГО БЛИЖЕ К 
ВЕРХНЕМУ КРАЮ СТРАНИЦЫ, ТОГДА КАК СЛОВО НА БУКВУ я БУДЕТ, ПО-ВИДИМОМУ, 
ПОМЕЩЕНО БЛИЖЕ К НИЖНЕМУ КРАЮ СТРАНИЦЫ И~Т.~Д. аНАЛОГИЧНЫЙ СПОСОБ 
ПРИМЕНЯЕТСЯ ПРИ РАССТАНОВКЕ КНИГ НА ПОЛКЕ ПО ФАМИЛИЯМ АВТОРОВ, ЕСЛИ КНИГИ 
БЕРУТСЯ С ПОЛА В СЛУЧАЙНОМ ПОРЯДКЕ: СТАВЯ КНИГУ НА ПОЛКУ, ВЫ ОЦЕНИВАЕТЕ ЕЕ 
КОНЕЧНОЕ ПОЛОЖЕНИЕ, СОКРАЩАЯ ТАКИМ ОБРАЗОМ ЧИСЛО НЕОБХОДИМЫХ СРАВНЕНИЙ И 
ПЕРЕМЕЩЕНИЙ. (эФФЕКТИВНОСТЬ ПРОЦЕССА ПОВЫШАЕТСЯ, ЕСЛИ НА ПОЛКЕ ИМЕЕТСЯ 
НЕМНОГО БОЛЬШЕ МЕСТА, ЧЕМ ЭТО АБСОЛЮТНО НЕОБХОДИМО.) тАКОЙ МЕТОД МАШИННОЙ 
СОРТИРОВКИ ВПЕРВЫЕ ПРЕДЛОЖИЛИ иСААК И сИНГЛТОН, 
[{\sl JACM\/},  {\bf 3} (1956), 169--174];
ОН ПОЛУЧИЛ ДАЛЬНЕЙШЕЕ РАЗВИТИЕ В РАБОТЕ кРОНМЭЛА И тАРТАРА 
[Proc. ACM Nat'l Conf., {\bf 21} (1966), 331--337].

сОРТИРОВКА С ВЫЧИСЛЕНИЕМ АДРЕСА ОБЫЧНО ТРЕБУЕТ ДОПОЛНИТЕЛЬНОГО 
ПРОСТРАНСТВА ПАМЯТИ ЛИБО ДЛЯ ТОГО, ЧТОБЫ ОСТАВИТЬ ДОСТАТОЧНО СВОБОДНОГО 
МЕСТА И НЕ ДЕЛАТЬ МНОГО ЛИШНИХ ПЕРЕМЕЩЕНИЙ, ЛИБО ДЛЯ ХРАНЕНИЯ 
ВСПОМОГАТЕЛЬНЫХ ТАБЛИЦ, КОТОРЫЕ БЫ ПОЗВОЛЯЛИ УЧИТЫВАТЬ НЕРАВНОМЕРНОСТЬ 
РАСПРЕДЕЛЕНИЯ КЛЮЧЕЙ. (сМ.\ СОРТИРОВКУ РАСПРЕДЕЛЯЮЩИМ ПОДСЧЕТОМ (АЛГОРИТМ~5.2D),
%% 124
\bye