\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