\input style
\chapnotrue
\chapno=5
\subchno=2
\subsubchno=2

\subsubchap{сОРТИРОВКА ПОСРЕДСТВОМ ВЫБОРА}
еЩЕ ОДНО ВАЖНОЕ СЕМЕЙСТВО МЕТОДОВ СОРТИРОВКИ ОСНОВАНО НА ИДЕЕ 
МНОГОКРАТНОГО ВЫБОРА. вЕРОЯТНО, ПРОСТЕЙШАЯ СОРТИРОВКА ПОСРЕДСТВОМ ВЫБОРА 
СВОДИТСЯ К СЛЕДУЮЩЕМУ:

\medskip
\item{i)} нАЙТИ НАИМЕНЬШИЙ КЛЮЧ; ПЕРЕСЛАТЬ СООТВЕТСТВУЮЩУЮ ЗАПИСЬ В 
ОБЛАСТЬ ВЫВОДА И ЗАМЕНИТЬ КЛЮЧ ЗНАЧЕНИЕМ "$\infty$" (КОТОРОЕ ПО 
ПРЕДПОЛОЖЕНИЮ БОЛЬШЕ ЛЮБОГО РЕАЛЬНОГО КЛЮЧА).

\item{ii)} пОВТОРИТЬ ШАГ (i). нА ЭТОТ РАЗ БУДЕТ ВЫБРАН КЛЮЧ,
НАИМЕНЬШИЙ ИЗ ОСТАВШИХСЯ, ТАК КАК РАНЕЕ НАИМЕНЬШИЙ КЛЮЧ БЫЛ ЗАМЕНЕН 
НА $\infty$.

\item{iii)} пОВТОРЯТЬ ШАГ (i) ДО ТЕХ ПОР, ПОКА НЕ БУДУТ ВЫБРАНЫ $N$ ЗАПИСЕЙ.
\medskip

\noindent
зАМЕТИМ, ЧТО ЭТОТ МЕТОД ТРЕБУЕТ НАЛИЧИЯ ВСЕХ ИСХОДНЫХ ЭЛЕМЕНТОВ ДО 
НАЧАЛА СОРТИРОВКИ, А ЭЛЕМЕНТЫ ВЫВОДА ОН ПОРОЖДАЕТ ПОСЛЕДОВАТЕЛЬНО, ОДИН ЗА 
ДРУГИМ. кАРТИНА, ПО СУЩЕСТВУ, ПРОТИВОПОЛОЖНА МЕТОДУ ВСТАВОК, В КОТОРОМ 
ИСХОДНЫЕ ЭЛЕМЕНТЫ ДОЛЖНЫ ПОСТУПАТЬ ПОСЛЕДОВАТЕЛЬНО, НО ВПЛОТЬ ДО 
ЗАВЕРШЕНИЯ СОРТИРОВКИ НИЧЕГО НЕ ИЗВЕСТНО ОБ ОКОНЧАТЕЛЬНОМ ВЫВОДЕ.

рЯД ВЫЧИСЛИТЕЛЬНЫХ МАШИН (НАПРИМЕР, МАШИНЫ С ЦИКЛИЧЕСКОЙ БАРАБАННОЙ 
ПАМЯТЬЮ) ИМЕЕТ ВСТРОЕННУЮ КОМАНДУ "НАЙТИ НАИМЕНЬШИЙ ЭЛЕМЕНТ", КОТОРАЯ 
ВЫПОЛНЯЕТСЯ С БОЛЬШОЙ СКОРОСТЬЮ. нА ТАКИХ МАШИНАХ СОРТИРОВКА УКАЗАННЫМ 
МЕТОДОМ ОСОБЕННО ПРИВЛЕКАТЕЛЬНА, ЕСЛИ ТОЛЬКО $N$ НЕ СЛИШКОМ ВЕЛИКО.

оПИСАННЫЙ МЕТОД ТРЕБУЕТ $N-1$ СРАВНЕНИЙ КАЖДЫЙ РАЗ, КОГДА ВЫБИРАЕТСЯ 
ОЧЕРЕДНАЯ ЗАПИСЬ; ОН ТАКЖЕ ТРЕБУЕТ ОТДЕЛЬНОЙ ОБЛАСТИ ВЫВОДА В ПАМЯТИ. 
иМЕЕТСЯ ОЧЕВИДНЫЙ СПОСОБ НЕСКОЛЬКО ПОПРАВИТЬ СИТУАЦИЮ, ИЗБЕЖАВ ПРИ ЭТОМ 
ИСПОЛЬЗОВАНИЯ $\infty$: ВЫБРАННОЕ ЗНАЧЕНИЕ МОЖНО ЗАПИСЫВАТЬ В 
СООТВЕТСТВУЮЩУЮ ПОЗИЦИЮ, А ЗАПИСЬ, КОТОРАЯ ЕЕ ЗАНИМАЛА, ПЕРЕНОСИТЬ 
НА МЕСТО ВЫБРАННОЙ. тОГДА ЭТУ ПОЗИЦИЮ НЕ НУЖНО РАССМАТРИВАТЬ ВНОВЬ ПРИ 
ПОСЛЕДУЮЩИХ ВЫБОРАХ. нА ЭТОЙ ИДЕЕ ОСНОВАН НАШ ПЕРВЫЙ АЛГОРИТМ СОРТИРОВКИ 
ПОСРЕДСТВОМ ВЫБОРА.

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

\st[цИКЛ ПО $j$.] вЫПОЛНИТЬ ШАГИ \stp{2} И \stp{3} ПРИ $j=N$, $N-1$, \dots, 2.
%% 170 

\st[нАЙТИ~$\max(K_1,~\ldots, K_j)$.] нАЙТИ НАИБОЛЬШИЙ ИЗ КЛЮЧЕЙ~$K_j$, 
$K_{j-1}$,~\dots, $K_1$; ПУСТЬ ЭТО БУДЕТ~$K_i$.

\st[пОМЕНЯТЬ МЕСТАМИ С~$R_j$.] вЗАИМОЗАМЕНИТЬ ЗАПИСИ~$R_i\xchg R_j$. 
(тЕПЕРЬ ЗАПИСИ~$R_j$,~\dots, $R_N$ ЗАНИМАЮТ СВОИ ОКОНЧАТЕЛЬНЫЕ ПОЗИЦИИ.)
\algend
\picture{рИС. ~21. сОРТИРОВКА ПРОСТЫМ ВЫБОРОМ.}

в ТАБЛ.~1 ПОКАЗАНО ДЕЙСТВИЕ ЭТОГО АЛГОРИТМА НА ШЕСТНАДЦАТЬ КЛЮЧЕЙ, 
ВЫБРАННЫХ НАМИ ДЛЯ ПРИМЕРОВ; ЭЛЕМЕНТЫ, ПРЕТЕНДУЮЩИЕ НА ТО, ЧТОБЫ 
ОКАЗАТЬСЯ МАКСИМАЛЬНЫМИ ВО ВРЕМЯ ПОИСКА В ШАГЕ~S2, ВЫДЕЛЕНЫ ЖИРНЫМ ШРИФТОМ.

{\catcode`\!=\active\def!#1.{{\bf #1}}
\htable{тАБЛИЦА 1}%
{сОРТИРОВКА ПОСРЕДСТВОМ ПРОСТОГО ВЫБОРА}%
{\strut\hfil$#$\hfil\bskip&&\bskip\hfil$#$\hfil\bskip\cr
503 & 087 & 512 & 061 &!908.& 170 &!897.& 275 & 653 & 426 & 154 & 509 & 612 & 677 &!765.&!703.\cr
503 & 087 & 512 & 061 & 703 & 170 &!897.& 275 & 653 & 426 & 154 & 509 & 612 & 677 &!765.& 908 \cr
503 & 087 & 512 & 061 & 703 & 170 &!765.& 275 & 653 & 426 & 154 & 509 & 612 &!677.& 897 & 908 \cr
503 & 087 & 512 & 061 &!703.& 170 &!677.& 275 &!653.& 426 & 154 & 509 &!612.& 765 & 897 & 908 \cr
503 & 087 & 512 & 061 & 612 & 170 &!677.& 275 &!653.& 426 & 154 &!509.& 703 & 765 & 897 & 908 \cr
503 & 087 & 512 & 061 & 612 & 170 & 509 & 275 &!653.&!426.&!154.& 677 & 703 & 765 & 897 & 908 \cr
\ldots\cr
061 &!087.& 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
}}

сООТВЕТСТВУЮЩАЯ \MIX-ПРОГРАММА ДОВОЛЬНО ПРОСТА.

\prog S.(сОРТИРОВКА ПОСРЕДСТВОМ ПРОСТОГО ВЫБОРА.)
кАК И В ПРЕДЫДУЩИХ ПРОГРАММАХ ЭТОЙ ГЛАВЫ, ЗАПИСИ, НАХОДЯЩИЕСЯ В ЯЧЕЙКАХ 
ОТ~$|INPUT|+1$ ДО~$|INPUT|+N$, СОРТИРУЮТСЯ НА ТОМ ЖЕ МЕСТЕ ПО КЛЮЧУ, 
ЗАНИМАЮЩЕМУ ПОЛНОЕ СЛОВО. зНАЧЕНИЯ РЕГИСТРОВ: $|rA|\equiv \hbox{ТЕКУЩИЙ 
МАКСИМУМ}$, $|rI1|\equiv j-1$, $|rI2|\equiv k$ (ИНДЕКС ПРИ ПОИСКЕ), 
$|rI3|\equiv i$. пРЕДПОЛАГАЕТСЯ, ЧТО~$N\ge 2$.
\code
START & ENT1 & N-1      & 1   & S1. цИКЛ ПО~$j$. $j\asg N$.
2H    & ENT2 & 0,1      & N-1 & S2. нАЙТИ~$\max(K_1, \ldots, K_j)$. $k\asg j-1$.
      & ENT3 & 1,1      & N-1 & $i\asg j$.
      & LDA  & INPUT,3  & N-1 & $|rA|\asg K_i$.
8H    & CMPA & INPUT,2  & A
      & JGE  & *+3      & A   & пЕРЕХОД, ЕСЛИ~$K_i\ge K_k$.
      & ENT3 & 0,2      & B   & в ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ~$i\asg k$,
%% 171
      & LDA  & INPUT, 3 & B   & $|rA|\asg K_i$.
      & DEC2 & 1        & A   & $k\asg k-1$.
      & J2P  & 8B       & A   & пОВТОРИТЬ, ЕСЛИ~$k>0$.
      & LDX  & INPUT+1,1& N-1 & S3. пОМЕНЯТЬ МЕСТАМИ С~$R_j$.
      & STX  & INPUT,3  & N-1 & $R_i\asg R_j$.
      & STA  & INPUT+1,1& N-1 & $R_j\asg |rA|$.
      & DEC1 & 1        & N-1 
      & J1P  & 2B       & N-1 & $N\ge j \ge 2$.
\endcode
\progend
вРЕМЯ РАБОТЫ ЭТОЙ ПРОГРАММЫ ЗАВИСИТ ОТ ЧИСЛА ЭЛЕМЕНТОВ~$N$, ЧИСЛА 
СРАВНЕНИЙ~$A$ И ЧИСЛА "ПРАВОСТОРОННИХ МАКСИМУМОВ"~$B$. нЕТРУДНО ВИДЕТЬ, 
ЧТО НЕЗАВИСИМО ОТ ЗНАЧЕНИЙ ИСХОДНЫХ КЛЮЧЕЙ
$$
A=\perm{N}{2}={1\over 2}N(N-1).
\eqno(1)
$$
сЛЕДОВАТЕЛЬНО, ПЕРЕМЕННОЙ ЯВЛЯЕТСЯ ТОЛЬКО ВЕЛИЧИНА~$B$. нЕСМОТРЯ НА ВСЮ 
БЕЗЫСКУСНОСТЬ ПРОСТОГО ВЫБОРА, НЕ ТАК ЛЕГКО ПРОИЗВЕСТИ ТОЧНЫЙ АНАЛИЗ 
ВЕЛИЧИНЫ~$B$. в УПР. С~3 ПО~6 ПОКАЗАНО, ЧТО
$$
B=(\min 0, \ave (N+1)H_n-2N, \max \floor{N^2/4});
\eqno(2)
$$
В ЭТОМ СЛУЧАЕ ОСОБЕННО ИНТЕРЕСНЫМ ОКАЗЫВАЕТСЯ МАКСИМАЛЬНОЕ ЗНАЧЕНИЕ 
(СТАНДАРТНОЕ ОТКЛОНЕНИЕ ВЕЛИЧИНЫ~$B$ ДО СИХ ПОР НЕ ОПРЕДЕЛЕНО).

тАКИМ ОБРАЗОМ, СРЕДНЕЕ ВРЕМЯ РАБОТЫ ПРОГРАММЫ~S 
РАВНО $2.5N^2+3(N+1)H_N+3.5N-11$~ЕДИНИЦ, Т.~Е.\ ОНА ЛИШЬ НЕМНОГИМ 
МЕДЛЕННЕЕ ПРОСТЫХ ВСТАВОК (ПРОГРАММА~5.2.1S). иНТЕРЕСНО СРАВНИТЬ 
АЛГОРИТМ~S С СОРТИРОВКОЙ МЕТОДОМ ПУЗЫРЬКА (АЛГОРИТМ~5.2.2в), ТАК КАК МЕТОД 
ПУЗЫРЬКА МОЖНО РАССМАТРИВАТЬ КАК АЛГОРИТМ ВЫБОРА, В КОТОРОМ ИНОГДА 
ВЫБИРАЕТСЯ БОЛЕЕ ОДНОГО ЭЛЕМЕНТА ЗА РАЗ. пО ЭТОЙ ПРИЧИНЕ ПРИ СОРТИРОВКЕ 
МЕТОДОМ ПУЗЫРЬКА ПРОИЗВОДИТСЯ МЕНЬШЕ СРАВНЕНИЙ, ЧЕМ ПРИ ПРОСТОМ ВЫБОРЕ, И 
ОНА, КАК МОЖЕТ ПОКАЗАТЬСЯ, ПРЕДПОЧТИТЕЛЬНЕЕ. нО В ДЕЙСТВИТЕЛЬНОСТИ 
ПРОГРАММА~5.2.2в БОЛЕЕ ЧЕМ ВДВОЕ МЕДЛЕННЕЕ ПРОГРАММЫ~S! сОРТИРОВКА МЕТОДОМ 
ПУЗЫРЬКА ПРОИГРЫВАЕТ ИЗ-ЗА ТОГО, ЧТО В НЕЙ ВЫПОЛНЯЕТСЯ СЛИШКОМ МНОГО 
ОБМЕНОВ, В ТО ВРЕМЯ КАК ПРИ СОРТИРОВКЕ ПРОСТЫМ ВЫБОРОМ ПРОИЗВОДИТСЯ ОЧЕНЬ МАЛО
ПЕРЕСЫЛОК ДАННЫХ.

\section уСОВЕРШЕНСТВОВАНИЯ ПРОСТОГО ВЫБОРА. сУЩЕСТВУЕТ ЛИ КАКОЙ-НИБУДЬ 
СПОСОБ УЛУЧШИТЬ МЕТОД ВЫБОРА, ИСПОЛЬЗУЕМЫЙ В АЛГОРИТМЕ~S? вОЗЬМЕМ К 
ПРИМЕРУ ПОИСК МАКСИМУМА В ШАГЕ~S2: ВОЗМОЖЕН ЛИ СУЩЕСТВЕННО БОЛЕЕ БЫСТРЫЙ 
СПОСОБ НАХОЖДЕНИЯ МАКСИМУМА? оТВЕТ НА ЭТОТ ВОПРОС---\emph{НЕТ!}

\proclaim лЕММА~M. в ЛЮБОМ АЛГОРИТМЕ НАХОЖДЕНИЯ МАКСИМУМА ИЗ 
$n$~ЭЛЕМЕНТОВ, ОСНОВАННОМ НА СРАВНЕНИИ ПАР ЭЛЕМЕНТОВ, 
НЕОБХОДИМО ВЫПОЛНИТЬ ПО КРАЙНЕЙ МЕРЕ $n-1$~СРАВНЕНИЙ.

%%172 

\proof еСЛИ ПРОИЗВЕДЕНО МЕНЕЕ $n-1$ СРАВНЕНИЙ, ТО НАЙДУТСЯ ПО КРАЙНЕЙ МЕРЕ 
ДВА ЭЛЕМЕНТА, ДЛЯ КОТОРЫХ НЕ БЫЛО ОБНАРУЖЕНО НИ ОДНОГО ЭЛЕМЕНТА, 
ПРЕВОСХОДЯЩЕГО ИХ ПО ВЕЛИЧИНЕ. сЛЕДОВАТЕЛЬНО, МЫ ТАК И НЕ УЗНАЕМ, 
КОТОРЫЙ ИЗ ЭТИХ ДВУХ ЭЛЕМЕНТОВ БОЛЬШЕ, И, ЗНАЧИТ, НЕ СМОЖЕМ ОПРЕДЕЛИТЬ МАКСИМУМ.
\proofend

тАКИМ ОБРАЗОМ, ПРОЦЕСС ВЫБОРА, В КОТОРОМ ОТЫСКИВАЕТСЯ НАИБОЛЬШИЙ ЭЛЕМЕНТ, 
ДОЛЖЕН СОСТОЯТЬ НЕ МЕНЕЕ ЧЕМ ИЗ $n-1$ ШАГОВ. оЗНАЧАЕТ ЛИ ЭТО, ЧТО ДЛЯ ВСЕХ 
МЕТОДОВ СОРТИРОВКИ, ОСНОВАННЫХ НА $n$ ПОВТОРНЫХ ВЫБОРАХ, ЧИСЛО ШАГОВ 
НЕИЗБЕЖНО БУДЕТ ПОРЯДКА $n^2$? к СЧАСТЬЮ, ЛЕММА M ПРИМЕНИМА ТОЛЬКО К 
\emph{ПЕРВОМУ} ШАГУ ВЫБОРА; ПРИ ПОСЛЕДУЮЩИХ ВЫБОРАХ МОЖНО 
ИСПОЛЬЗОВАТЬ ИЗВЛЕЧЕННУЮ РАНЕЕ ИНФОРМАЦИЮ. нАПРИМЕР, В УПР.~8 ПОКАЗАНО,
 ЧТО СРАВНИТЕЛЬНО ПРОСТОЕ ИЗМЕНЕНИЕ АЛГОРИТМА~S НАПОЛОВИНУ СОКРАЩАЕТ ЧИСЛО СРАВНЕНИЙ.

рАССМОТРИМ 16 ЧИСЕЛ, ПРЕДСТАВЛЕННЫХ В 1-Й СТРОКЕ В ТАБЛ.~1. оДИН ИЗ 
СПОСОБОВ СЭКОНОМИТЬ ВРЕМЯ ПРИ ПОСЛЕДУЮЩИХ 
ВЫБОРАХ---РАЗБИТЬ ВСЕ ЧИСЛА НА ЧЕТЫРЕ ГРУППЫ ПО ЧЕТЫРЕ ЧИСЛА. нАЧАТЬ МОЖНО С 
ОПРЕДЕЛЕНИЯ НАИБОЛЬШЕГО, ЭЛЕМЕНТА КАЖДОЙ ГРУППЫ, А ИМЕННО СООТВЕТСТВЕННО С КЛЮЧЕЙ
$$
512, 908, 653, 765;
$$
ТОГДА НАИБОЛЬШИЙ ИЗ ЭТИХ ЧЕТЫРЕХ ЭЛЕМЕНТОВ 908 И БУДЕТ НАИБОЛЬШИМ ВО 
ВСЕМ ФАЙЛЕ. чТОБЫ ПОЛУЧИТЬ ВТОРОЙ ПО ВЕЛИЧИНЕ ЭЛЕМЕНТ, ДОСТАТОЧНО 
ПРОСМОТРЕТЬ СНАЧАЛА ОСТАЛЬНЫЕ ТРИ ЭЛЕМЕНТА ГРУППЫ, СОДЕРЖАЩЕЙ 908; 
НАИБОЛЬШИЙ ИЗ $\{170, 897, 275\}$ РАВЕН 897, И ТОГДА НАИБОЛЬШИЙ СРЕДИ
$$
512, 897, 653, 765
$$
ЭТО 897. аНАЛОГИЧНО, ДЛЯ ТОГО ЧТОБЫ ПОЛУЧИТЬ ТРЕТИЙ ПО ВЕЛИЧИНЕ ЭЛЕМЕНТ, 
ОПРЕДЕЛЯЕМ НАИБОЛЬШИЙ ИЗ $\{170, 275\}$, А ЗАТЕМ НАИБОЛЬШИЙ ИЗ
$$
512, 275, 653, 765
$$
И Т. Д. кАЖДЫЙ ВЫБОР, КРОМЕ ПЕРВОГО, ТРЕБУЕТ НЕ БОЛЕЕ 6 ДОПОЛНИТЕЛЬНЫХ 
СРАВНЕНИЙ. вООБЩЕ, ЕСЛИ $N$---ТОЧНЫЙ КВАДРАТ, ТО МОЖНО РАЗДЕЛИТЬ ФАЙЛ НА 
$\sqrt N$ ГРУПП ПО $\sqrt N$ ЭЛЕМЕНТОВ В КАЖДОЙ;
ЛЮБОЙ ВЫБОР, КРОМЕ ПЕРВОГО, ТРЕБУЕТ НЕ БОЛЕЕ ЧЕМ $\sqrt{N}-1$ СРАВНЕНИЙ 
ВНУТРИ ГРУППЫ РАНЕЕ ВЫБРАННОГО ЭЛЕМЕНТА ПЛЮС $\sqrt{N}-1$ СРАВНЕНИЙ СРЕДИ 
"ЛИДЕРОВ ГРУПП". эТОТ МЕТОД ПОЛУЧИЛ НАЗВАНИЕ "КВАДРАТИЧНЫЙ ВЫБОР"; ОБЩЕЕ 
ВРЕМЯ РАБОТЫ ДЛЯ НЕГО ЕСТЬ $O(N\sqrt{N})$, ЧТО СУЩЕСТВЕННО ЛУЧШЕ, ЧЕМ $O(N^2)$.

мЕТОД КВАДРАТИЧНОГО ВЫБОРА ВПЕРВЫЕ ОПУБЛИКОВАН 
э.~X.~фРЭНДОМ [{\sl JACM\/}, {\bf 3} (1956), 152--154]; ОН УКАЗАЛ, ЧТО ЭТУ 
ИДЕЮ МОЖНО ОБОБЩИТЬ, ПОЛУЧИВ В РЕЗУЛЬТАТЕ МЕТОД КУБИЧЕСКОГО ВЫБОРА,
ВЫБОРА ЧЕТВЕРТОЙ СТЕПЕНИ И Т. Д. нАПРИМЕР, МЕТОД КУБИЧЕСКОГО
%%173
ВЫБОРА СОСТОИТ В ТОМ, ЧТОБЫ РАЗДЕЛИТЬ ФАЙЛ НА $\root 3\of N$ БОЛЬШИХ ГРУПП,
 КАЖДАЯ ИЗ КОТОРЫХ СОДЕРЖИТ ПО $\root 3\of N$ МАЛЫХ ГРУПП ПО $\root 3\of 
N$ ЗАПИСЕЙ; ВРЕМЯ РАБОТЫ ПРОПОРЦИОНАЛЬНО $N\root 3\of N$. еСЛИ РАЗВИТЬ 
ЭТУ ИДЕЮ ДО ЕЕ ПОЛНОГО ЗАВЕРШЕНИЯ, ТО МЫ ПРИДЕМ К ТОМУ, ЧТО фРЭНД НАЗВАЛ 
"ВЫБОР $n$-Й СТЕПЕНИ", ОСНОВАННЫЙ НА СТРУКТУРЕ БИНАРНОГО ДЕРЕВА. вРЕМЯ 
РАБОТЫ ЭТОГО МЕТОДА ПРОПОРЦИОНАЛЬНО $N \log N$; МЫ БУДЕМ НАЗЫВАТЬ ЕГО 
\dfn{ВЫБОРОМ ИЗ ДЕРЕВА}.
\section вЫБОР ИЗ ДЕРЕВА. пРИНЦИПЫ СОРТИРОВКИ ПОСРЕДСТВОМ ВЫБОРА ИЗ ДЕРЕВА 
БУДЕТ ЛЕГЧЕ ВОСПРИНЯТЬ, ЕСЛИ ВОСПОЛЬЗОВАТЬСЯ АНАЛОГИЕЙ С ТИПИЧНЫМ 
"ТУРНИРОМ С ВЫБЫВАНИЕМ". рАССМОТРИМ, НАПРИМЕР, РЕЗУЛЬТАТЫ СОРЕВНОВАНИЯ 
ПО НАСТОЛЬНОМУ ТЕННИСУ, ПОКАЗАННЫЕ НА РИС.~22. дЖИМ ПОБЕЖДАЕТ дОНА, А 
дЖО ПОБЕЖДАЕТ дЖЕКА; ЗАТЕМ В СЛЕДУЮЩЕМ ТУРЕ дЖО ВЫИГРЫВАЕТ У дЖИМА И Т. Д.

нА РИС.~22 ПОКАЗАНО, ЧТО дЖО---ЧЕМПИОН СРЕДИ ВОСЬМИ СПОРТСМЕНОВ, А ДЛЯ 
ТОГО, ЧТОБЫ ОПРЕДЕЛИТЬ ЭТО, ПОТРЕБОВАЛОСЬ $8-1=7$ МАТЧЕЙ (Т. Е. СРАВНЕНИЙ).
 дИК ВОВСЕ НЕ ОБЯЗАТЕЛЬНО БУДЕТ ВТОРЫМ ПО СИЛЕ ИГРОКОМ: ЛЮБОЙ ИЗ 
СПОРТСМЕНОВ, У КОТОРЫХ ВЫИГРАЛ дЖО, ВКЛЮЧАЯ ДАЖЕ ПРОИГРАВШЕГО В ПЕРВОМ 
ТУРЕ дЖЕКА, МОГ БЫ ОКАЗАТЬСЯ ВТОРЫМ ПО СИЛЕ ИГРОКОМ. вТОРОГО ИГРОКА МОЖНО 
ОПРЕДЕЛИТЬ, ЗАСТАВИВ дЖЕКА СЫГРАТЬ С дЖИМОМ, А ПОБЕДИТЕЛЯ ЭТОГО МАТЧА---С 
дИКОМ; ВСЕГО ДВА ДОПОЛНИТЕЛЬНЫХ МАТЧА ТРЕБУЕТСЯ ДЛЯ ОПРЕДЕЛЕНИЯ ВТОРОГО ПО 
СИЛЕ ИГРОКА, ИСХОДЯ ИЗ ТОГО СООТНОШЕНИЯ СИЛ, КОТОРОЕ МЫ ЗАПОМНИЛИ ИЗ 
ПРЕДЫДУЩИХ ИГР.

вООБЩЕ МОЖНО "ВЫВЕСТИ" ИГРОКА, НАХОДЯЩЕГОСЯ В КОРНЕ ДЕРЕВА, И ЗАМЕНИТЬ ЕГО 
ЧРЕЗВЫЧАЙНО СЛАБЫМ ИГРОКОМ. пОДСТАНОВКА ЭТОГО СЛАБОГО ИГРОКА ОЗНАЧАЕТ, 
ЧТО ПЕРВОНАЧАЛЬНО ВТОРОЙ ПО СИЛЕ СПОРТСМЕН СТАНЕТ ТЕПЕРЬ НАИЛУЧШИМ, И 
ИМЕННО ОН ОКАЖЕТСЯ В КОРНЕ, ЕСЛИ ВНОВЬ ВЫЧИСЛИТЬ ПОБЕДИТЕЛЕЙ В 
ВЕРХНИХ УРОВНЯХ ДЕРЕВА. дЛЯ ЭТОГО НУЖНО ИЗМЕНИТЬ ЛИШЬ ОДИН ПУТЬ, В ДЕРЕВЕ, 
ТАК ЧТО ДЛЯ ВЫБОРА СЛЕДУЮЩЕГО ПО СИЛЕ ИГРОКА НЕОБХОДИМО МЕНЕЕ $\lceil 
\log_2 N\rceil$) ДОПОЛНИТЕЛЬНЫХ СРАВНЕНИЙ. сУММАРНОЕ
%%174
\picture{рИС. 23. пРИМЕР СОРТИРОВКИ ПОСРЕДСТВОМ ВЫБОРА ИЗ ДЕРЕВА...}
%% 175
ВРЕМЯ ВЫПОЛНЕНИЯ ТАКОЙ СОРТИРОВКИ ПОСРЕДСТВОМ ВЫБОРА ПРИМЕРНО 
ПРОПОРЦИОНАЛЬНО $N\log N$.

нА РИС.~23 СОРТИРОВКЕ ПОСРЕДСТВОМ ВЫБОРА ИЗ ДЕРЕВА ПОДВЕРГАЮТСЯ НАШИ 16 
ЧИСЕЛ. зАМЕТИМ, ЧТО ДЛЯ ТОГО, ЧТОБЫ ЗНАТЬ, КУДА ВСТАВЛЯТЬ СЛЕДУЮЩИЙ 
ЭЛЕМЕНТ "$-\infty$", НЕОБХОДИМО ПОМНИТЬ, ОТКУДА ПРИШЕЛ КЛЮЧ, НАХОДЯЩИЙСЯ В 
КОРНЕ. пОЭТОМУ УЗЛЫ РАЗВЕТВЛЕНИЯ В ДЕЙСТВИТЕЛЬНОСТИ СОДЕРЖАТ УКАЗАТЕЛИ 
ИЛИ ИНДЕКСЫ, ОПИСЫВАЮЩИЕ ПОЗИЦИЮ КЛЮЧА, А НЕ САМ КЛЮЧ. оТСЮДА СЛЕДУЕТ, ЧТО 
НЕОБХОДИМА ПАМЯТЬ ДЛЯ $N$ ИСХОДНЫХ ЗАПИСЕЙ, $N-1$ СЛОВ-УКАЗАТЕЛЕЙ И $N$ 
ВЫВОДИМЫХ ЗАПИСЕЙ. (рАЗУМЕЕТСЯ, ЕСЛИ ВЫВОД
\picture{рИС. 24.  пРИМЕНЕНИЕ КОРПОРАТИВНОЙ СИСТЕМЫ ВЫДВИЖЕНИЙ К 
СОРТИРОВКЕ. кАЖДЫЙ ПОДНИМАЕТСЯ НА СВОЙ УРОВЕНЬ НЕКОМПЕТЕНТНОСТИ В ИЕРАРХИИ.}
ИДЕТ НА ЛЕНТУ ИЛИ НА ДИСК, ТО НЕ НУЖНО СОХРАНЯТЬ ВЫВОДИМЫЕ ЗАПИСИ В 
ОПЕРАТИВНОЙ ПАМЯТИ.)

чТОБЫ ОЦЕНИТЬ ТЕ ЗАМЕЧАТЕЛЬНЫЕ УСОВЕРШЕНСТВОВАНИЯ, КОТОРЫЕ МЫ СОБИРАЕМСЯ 
ОБСУДИТЬ, В ЭТОМ МЕСТЕ СЛЕДУЕТ ПРЕРВАТЬ ЧТЕНИЕ ДО ТЕХ ПОР, ПОКА ВЫ НЕ 
ОСВОИТЕСЬ С ВЫБОРОМ ИЗ ДЕРЕВА ХОТЯ БЫ НАСТОЛЬКО, ЧТО РЕШЕНИЕ УПР.~10 НЕ 
СОСТАВИТ ДЛЯ ВАС НИКАКОГО ТРУДА.

оДНА ИЗ МОДИФИКАЦИЙ ВЫБОРА ИЗ ДЕРЕВА, ВВЕДЕННАЯ, ПО СУЩЕСТВУ, 
к.~э.~аЙВЕРСОНОМ [A Programming Language (Wiley, 1962), 223--227], 
УСТРАНЯЕТ НЕОБХОДИМОСТЬ УКАЗАТЕЛЕЙ, СЛЕДУЮЩИМ ОБРАЗОМ ОСУЩЕСТВЛЯЯ 
"ЗАГЛЯДЫВАНИЕ ВПЕРЕД": КОГДА ПОБЕДИТЕЛЬ МАТЧА НА НИЖНЕМ УРОВНЕ ПОДНИМАЕТСЯ 
ВВЕРХ, ТО НА НИЖНЕМ УРОВНЕ ЕГО СРАЗУ ЖЕ МОЖНО ЗАМЕНИТЬ НА "$-\infty$"; 
КОГДА ЖЕ ПОБЕДИТЕЛЬ ПЕРЕМЕЩАЕТСЯ ВВЕРХ С ОДНОГО РАЗВЕТВЛЕНИЯ НА ДРУГОЕ,
 ТО ЕГО МОЖНО ЗАМЕНИТЬ ИГРОКОМ, КОТОРЫЙ В КОНЦЕ КОНЦОВ ВСЕ РАВНО ДОЛЖЕН 
ПОДНЯТЬСЯ, НА ЕГО ПРЕЖНЕЕ МЕСТО (А ИМЕННО НАИБОЛЬШИМ ИЗ ДВУХ КЛЮЧЕЙ, 
РАСПОЛОЖЕННЫХ ПОД НИМ). вЫПОЛНИВ ЭТУ ОПЕРАЦИЮ СТОЛЬКО РАЗ, СКОЛЬКО 
ВОЗМОЖНО, ПРИДЕМ ОТ РИС.~23(А) К РИС.~24.

кОЛЬ СКОРО ДЕРЕВО ПОСТРОЕНО ТАКИМ ОБРАЗОМ, МОЖНО ПРОДОЛЖАТЬ СОРТИРОВКУ 
НЕ "ВОСХОДЯЩИМ" МЕТОДОМ, ПОКАЗАННЫМ НА РИС.~23, А "НИСХОДЯЩИМ": ВЫВОДИТСЯ 
ЭЛЕМЕНТ, НАХОДЯЩИЙСЯ
%% 176
В КОРНЕ, ПЕРЕМЕЩАЕТСЯ ВВЕРХ НАИБОЛЬШИЙ ИЗ ЕГО ПОТОМКОВ, ПЕРЕМЕЩАЕТСЯ ВВЕРХ 
НАИБОЛЬШИЙ ИЗ ПОТОМКОВ ПОСЛЕДНЕГО И Т. Д. пРОЦЕСС НАЧИНАЕТ ПОХОДИТЬ НЕ 
СТОЛЬКО НА ТУРНИР ПО НАСТОЛЬНОМУ ТЕННИСУ, СКОЛЬКО НА КОРПОРАТИВНУЮ СИСТЕМУ ВЫДВИЖЕНИЙ.

чИТАТЕЛЬ ДОЛЖЕН УЯСНИТЬ, ЧТО У НИСХОДЯЩЕГО МЕТОДА ЕСТЬ ВАЖНОЕ 
ДОСТОИНСТВО---ОН ПОЗВОЛЯЕТ ИЗБЕЖАТЬ ЛИШНИХ СРАВНЕНИЙ $-\infty$ С~$-\infty$. 
(пОЛЬЗУЯСЬ ВОСХОДЯЩИМ МЕТОДОМ, МЫ НА БОЛЕЕ ПОЗДНИХ СТАДИЯХ СОРТИРОВКИ 
ВСЮДУ НАТЫКАЕМСЯ НА $-\infty$, А ПРИ НИСХОДЯЩЕМ МЕТОДЕ МОЖНО НА КАЖДОЙ 
СТАДИИ ЗАКАНЧИВАТЬ ПРЕОБРАЗОВАНИЕ ДЕРЕВА СРАЗУ ЖЕ ПОСЛЕ ЗАНЕСЕНИЯ $-\infty$.)
\picture{рИС. 25. пОСЛЕДОВАТЕЛЬНОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ ДЛЯ 
ПОЛНОГО БИНАРНОГО ДЕРЕВА.}

нА РИС.~23 И~24 ИЗОБРАЖЕНЫ \emph{ПОЛНЫЕ БИНАРНЫЕ ДЕРЕВЬЯ} С 16 КОНЦЕВЫМИ 
УЗЛАМИ (СР. С П.~2.3.4.5); ТАКИЕ ДЕРЕВЬЯ УДОБНО ХРАНИТЬ В 
ПОСЛЕДОВАТЕЛЬНЫХ ЯЧЕЙКАХ ПАМЯТИ, КАК ПОКАЗАНО НА РИС.~25. зАМЕТИМ, ЧТО 
ОТЦОМ УЗЛА НОМЕР $k$ ЯВЛЯЕТСЯ УЗЕЛ $\lfloor k/2\rfloor$ , А ЕГО ПОТОМКАМИ 
ЯВЛЯЮТСЯ УЗЛЫ $2k$ И $2k+1$. оТСЮДА ВЫТЕКАЕТ ЕЩЕ ОДНО ПРЕИМУЩЕСТВО 
НИСХОДЯЩЕГО МЕТОДА, ПОСКОЛЬКУ ЗАЧАСТУЮ ЗНАЧИТЕЛЬНО ПРОЩЕ ПРОДВИГАТЬСЯ ВНИЗ 
ОТ УЗЛА $k$ К УЗЛАМ $2k$ И~$2k+1$, ЧЕМ ВВЕРХ ОТ УЗЛА $k$ К УЗЛАМ $k\oplus 
1$ 
И~$\lfloor k/2\rfloor$. (зДЕСЬ ЧЕРЕЗ $k\oplus 1$ ОБОЗНАЧЕНО ЧИСЛО $k+1$ 
ИЛИ $k-1$ В ЗАВИСИМОСТИ ОТ  ТОГО, ЯВЛЯЕТСЯ ЛИ $k$ ЧЕТНЫМ ИЛИ НЕЧЕТНЫМ.)

дО СИХ ПОР В НАШИХ ПРИМЕРАХ ВЫБОРА ИЗ ДЕРЕВА В ТОЙ ИЛИ ИНОЙ МЕРЕ 
ПРЕДПОЛАГАЛОСЬ, ЧТО $N$ ЕСТЬ СТЕПЕНЬ 2; В ДЕЙСТВИТЕЛЬНОСТИ МОЖНО 
РАБОТАТЬ С ПРОИЗВОЛЬНЫМ ЗНАЧЕНИЕМ $N$, ТАК КАК ПОЛНОЕ БИНАРНОЕ ДЕРЕВО С 
$N$ КОНЦЕВЫМИ УЗЛАМИ НЕТРУДНО ПОСТРОИТЬ ДЛЯ ЛЮБОГО N. 

 мЫ ПОДОШЛИ ТЕПЕРЬ К ОСНОВНОМУ ВОПРОСУ: НЕЛЬЗЯ ЛИ В НИСХОДЯЩЕМ МЕТОДЕ 
ОБОЙТИСЬ СОВСЕМ БЕЗ "$-\infty$"? нЕ ПРАВДА ЛИ, БЫЛО БЫ ЧУДЕСНО, ЕСЛИ БЫ 
ВСЮ СУЩЕСТВЕННУЮ ИНФОРМАЦИЮ, ИМЕЮЩУЮСЯ НА РИС.~24, УДАЛОСЬ РАСПОЛОЖИТЬ В 
ЯЧЕЙКАХ 1--16
%%177
ПОЛНОГО БИНАРНОГО ДЕРЕВА БЕЗ ВСЯКИХ БЕСПОЛЕЗНЫХ "ДЫР", СОДЕРЖАЩИХ 
$-\infty$? пОРАЗМЫСЛИВ, МОЖНО ПРИЙТИ К ВЫВОДУ, ЧТО ЭТА ЦЕЛЬ В 
ДЕЙСТВИТЕЛЬНОСТИ ДОСТИЖИМА, ПРИЧЕМ НЕ ТОЛЬКО ИСКЛЮЧАЕТСЯ $-\infty$, НО И 
ПОЯВЛЯЕТСЯ ВОЗМОЖНОСТЬ СОРТИРОВАТЬ $N$ ЗАПИСЕЙ НА ТОМ ЖЕ МЕСТЕ БЕЗ 
ВСПОМОГАТЕЛЬНОЙ ОБЛАСТИ ВЫВОДА. эТО ПРИВОДИТ К ЕЩЕ ОДНОМУ ВАЖНОМУ 
АЛГОРИТМУ СОРТИРОВКИ. еГО АВТОР дЖ.~у.~дЖ.~уИЛЬЯМС [{\sl CACM\/}, {\bf 7} 
(1964), 347--348] ОКРЕСТИЛ СВОЙ АЛГОРИТМ "ПИРАМИДАЛЬНОЙ СОРТИРОВКОЙ" ("heapsort").

\section пИРАМИДАЛЬНАЯ СОРТИРОВКА.  бУДЕМ НАЗЫВАТЬ ФАЙЛ КЛЮЧЕЙ $K_1$, 
$K_2$, \dots, $K_N$ "ПИРАМИДОЙ", ЕСЛИ
$$
K_{\lfloor j/2\rfloor}\ge K_j \rem{ ПРИ $1\le \lfloor j/2\rfloor<j\le N$.}
\eqno(3)
$$
в ЭТОМ СЛУЧАЕ $K_1\ge K_2$, $K_1\ge K_3$, $K_2\ge K_4$ И Т.Д.; ИМЕННО ЭТО 
УСЛОВИЕ ВЫПОЛНЯЕТСЯ НА РИС.~24. иЗ НЕГО СЛЕДУЕТ, В ЧАСТНОСТИ, ЧТО 
НАИБОЛЬШИЙ КЛЮЧ ОКАЗЫВАЕТСЯ "НА ВЕРШИНЕ ПИРАМИДЫ":
$$
K_1=\max(K_1, K_2, \ldots, K_N).
\eqno(4)
$$
еСЛИ БЫ МЫ СУМЕЛИ КАК-НИБУДЬ ПРЕОБРАЗОВАТЬ ПРОИЗВОЛЬНЫЙ ИСХОДНЫЙ ФАЙЛ В 
ПИРАМИДУ, ТО ДЛЯ ПОЛУЧЕНИЯ ЭФФЕКТИВНОГО АЛГОРИТМА СОРТИРОВКИ МОЖНО БЫЛО БЫ 
ВОСПОЛЬЗОВАТЬСЯ "НИСХОДЯЩЕЙ" ПРОЦЕДУРОЙ ВЫБОРА, ПОДОБНОЙ ТОЙ, КОТОРАЯ 
ОПИСАНА ВЫШЕ.

эФФЕКТИВНЫЙ ПОДХОД К ЗАДАЧЕ ПОСТРОЕНИЯ ПИРАМИДЫ ПРЕДЛОЖИЛ р.~у.~фЛОЙД 
[{\sl CACM\/}, {\bf 7} (1964), 701]. пУСТЬ НАМ УДАЛОСЬ РАСПОЛОЖИТЬ ФАЙЛ 
ТАКИМ ОБРАЗОМ, ЧТО
$$
K_{\lfloor j/2\rfloor}\ge K_j \rem{ ПРИ $l < \lfloor j/2\rfloor<j\le N$,}
\eqno(5)
$$
ГДЕ $l$---НЕКОТОРОЕ ЧИСЛО $\ge1$. (в ИСХОДНОМ ФАЙЛЕ ЭТО УСЛОВИЕ ВЫПОЛНЯЕТСЯ 
"АВТОМАТИЧЕСКИ" ДЛЯ $l=\floor{N/2}$, ПОСКОЛЬКУ НИ ОДИН ИНДЕКС $j$ НЕ 
УДОВЛЕТВОРЯЕТ УСЛОВИЮ $\floor{N/2}<\floor{j/2}<j\le N$.) 
нЕТРУДНО ПОНЯТЬ, КАК, ИЗМЕНЯЯ ЛИШЬ ПОДДЕРЕВО С КОРНЕМ В УЗЛЕ $l$, 
ПРЕОБРАЗОВАТЬ ФАЙЛ, ЧТОБЫ РАСПРОСТРАНИТЬ НЕРАВЕНСТВА (5) И НА СЛУЧАЙ, 
КОГДА $\floor{j/2}=l$. сЛЕДОВАТЕЛЬНО, МОЖНО УМЕНЬШАТЬ $l$ НА ЕДИНИЦУ, ПОКА В 
КОНЦЕ КОНЦОВ НЕ БУДЕТ ДОСТИГНУТО УСЛОВИЕ (3). эТИ ИДЕИ уИЛЬЯМСА И фЛОЙДА 
ПРИВОДЯТ К ИЗЯЩНОМУ АЛГОРИТМУ, КОТОРЫЙ ЗАСЛУЖИВАЕТ ПРИСТАЛЬНОГО ИЗУЧЕНИЯ.

\alg H.(пИРАМИДАЛЬНАЯ СОРТИРОВКА.) зАПИСИ $R_1$, \dots, 
$R_N$ ПЕРЕРАЗМЕЩАЮТСЯ НА ТОМ ЖЕ МЕСТЕ; ПОСЛЕ ЗАВЕРШЕНИЯ СОРТИРОВКИ ИХ 
КЛЮЧИ БУДУТ УПОРЯДОЧЕНЫ: $K_1\le \ldots \le K_N$. сНАЧАЛА 
ФАЙЛ ПЕРЕСТРАИВАЕТСЯ В ПИРАМИДУ, ПОСЛЕ ЧЕГО ВЕРШИНА ПИРАМИДЫ МНОГОКРАТНО 
ИСКЛЮЧАЕТСЯ И ЗАПИСЫВАЕТСЯ НА СВОЕ ОКОНЧАТЕЛЬНОЕ МЕСТО. пРЕДПОЛАГАЕТСЯ, 
ЧТО $N\ge2$.
\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $l\asg\floor{N/2}+1$, $r\asg N$.
\st[уМЕНЬШИТЬ $l$ ИЛИ~$r$.] еСЛИ. $l>1$, ТО УСТАНОВИТЬ $l\asg l-1$, $R\asg 
R_l$, $K\asg K_l$. (еСЛИ  $l>1$, ЭТО ОЗНАЧАЕТ, ЧТО ПРОИСХОДИТ
%% 178
ПРОЦЕСС ПРЕОБРАЗОВАНИЯ ИСХОДНОГО ФАЙЛА В ПИРАМИДУ; ЕСЛИ ЖЕ $l= 1$, ТО ЭТО 
ЗНАЧИТ, ЧТО КЛЮЧИ $K_1$, $K_2$, \dots, $K_r$ УЖЕ ОБРАЗУЮТ ПИРАМИДУ.) в 
ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ $R\asg R_r$, $K\asg K_r$, $R_r\asg R_1$  И 
$r\asg r-1$; ЕСЛИ В РЕЗУЛЬТАТЕ ОКАЗАЛОСЬ, ЧТО $r=1$, ТО УСТАНОВИТЬ 
$R_1\asg R$ И ЗАВЕРШИТЬ РАБОТУ АЛГОРИТМА.

\st[пРИГОТОВИТЬСЯ К "ПРОТАСКИВАНИЮ".] уСТАНОВИТЬ $j\asg l$. 
(к ЭТОМУ МОМЕНТУ
$$
K_\floor{j/2}\ge K_j \rem{ПРИ $l<\floor{j/2}<j\le r$,}
\eqno(6)
$$
А ЗАПИСИ $R_k$, $r<k\le N$, ЗАНИМАЮТ СВОИ ОКОНЧАТЕЛЬНЫЕ МЕСТА. шАГИ 
\stp{3}--\stp{8} НАЗЫВАЮТСЯ АЛГОРИТМОМ "ПРОТАСКИВАНИЯ"; ИХ
\picture{рИС. 26. пИРАМИДАЛЬНАЯ СОРТИРОВКА; ПУНКТИРОМ ОБВЕДЕН АЛГОРИТМ "ПРОТАСКИВАНИЯ".}
ДЕЙСТВИЕ ЭКВИВАЛЕНТНО УСТАНОВКЕ $R_l\asg R$ С ПОСЛЕДУЮЩИМ ПЕРЕМЕЩЕНИЕМ 
ЗАПИСЕЙ $R_l$, \dots, $R_r$ ТАКИМ ОБРАЗОМ, ЧТОБЫ УСЛОВИЕ (6) ВЫПОЛНЯЛОСЬ И 
ПРИ $\floor{j/2}=l$.)

\st[пРОДВИНУТЬСЯ ВНИЗ.] уСТАНОВИТЬ $i\asg j$ И $j\asg 2j$. (в ПОСЛЕДУЮЩИХ 
ШАГАХ $i = \floor{j/2}$.) еСЛИ $j< r$, ТО ПЕРЕЙТИ К ШАГУ \stp{5};
ЕСЛИ $j=r$, ТО ПЕРЕЙТИ К ШАГУ \stp{6}; ЕСЛИ ЖЕ $j>r$, ТО ПЕРЕЙТИ К ШАГУ \stp{8}.

\st[нАЙТИ "БОЛЬШЕГО" СЫНА.] еСЛИ $K_j<K_{j+1}$, ТО УСТАНОВИТЬ
$j\asg j+1$.

\st[бОЛЬШЕ $K$?] еСЛИ $K\ge K_j$, ТО ПЕРЕЙТИ К ШАГУ \stp{8}. 
\st[пОДНЯТЬ ЕГО ВВЕРХ.] уСТАНОВИТЬ $R_i\asg R_j$ И ВОЗВРАТИТЬСЯ
К ШАГУ \stp{4}.

\st[зАНЕСТИ $R$.] уСТАНОВИТЬ $R_i\asg R$. (нА ЭТОМ АЛГОРИТМ 
"ПРОТАСКИВАНИЯ", НАЧАТЫЙ В ШАГЕ \stp{з}, ЗАКАНЧИВАЕТСЯ.) вОЗВРАТИТЬСЯ 
К ШАГУ \stp{2}.
\algend
%%179
\bye