\input style
\chapnotrue
\chapno=5
\subchno=2
\subsubchno=2
%% 169
\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 
\algend
\bye