\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