\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