\input style
\chapnotrue
\chapno=5
\subchno=2
\subsubchno=2
%% 169
\subsubchap{sORTIROVKA POSREDSTVOM VYBORA}
eSHCHE ODNO VAZHNOE SEMEJSTVO METODOV SORTIROVKI OSNOVANO NA IDEE 
MNOGOKRATNOGO VYBORA. vEROYATNO, PROSTEJSHAYA SORTIROVKA POSREDSTVOM VYBORA 
SVODITSYA K SLEDUYUSHCHEMU:

\medskip
\item{i)} nAJTI NAIMENXSHIJ KLYUCH; PERESLATX SOOTVETSTVUYUSHCHUYU ZAPISX V 
OBLASTX VYVODA I ZAMENITX KLYUCH ZNACHENIEM "$\infty$" (KOTOROE PO 
PREDPOLOZHENIYU BOLXSHE LYUBOGO REALXNOGO KLYUCHA).

\item{ii)} pOVTORITX SHAG (i). nA |TOT RAZ BUDET VYBRAN KLYUCH,
NAIMENXSHIJ IZ OSTAVSHIHSYA, TAK KAK RANEE NAIMENXSHIJ KLYUCH BYL ZAMENEN 
NA $\infty$.

\item{iii)} pOVTORYATX SHAG (i) DO TEH POR, POKA NE BUDUT VYBRANY $N$ ZAPISEJ.
\medskip

\noindent
zAMETIM, CHTO |TOT METOD TREBUET NALICHIYA VSEH ISHODNYH |LEMENTOV DO 
NACHALA SORTIROVKI, A |LEMENTY VYVODA ON POROZHDAET POSLEDOVATELXNO, ODIN ZA 
DRUGIM. kARTINA, PO SUSHCHESTVU, PROTIVOPOLOZHNA METODU VSTAVOK, V KOTOROM 
ISHODNYE |LEMENTY DOLZHNY POSTUPATX POSLEDOVATELXNO, NO VPLOTX DO 
ZAVERSHENIYA SORTIROVKI NICHEGO NE IZVESTNO OB OKONCHATELXNOM VYVODE.

rYAD VYCHISLITELXNYH MASHIN (NAPRIMER, MASHINY S CIKLICHESKOJ BARABANNOJ 
PAMYATXYU) IMEET VSTROENNUYU KOMANDU "NAJTI NAIMENXSHIJ |LEMENT", KOTORAYA 
VYPOLNYAETSYA S BOLXSHOJ SKOROSTXYU. nA TAKIH MASHINAH SORTIROVKA UKAZANNYM 
METODOM OSOBENNO PRIVLEKATELXNA, ESLI TOLXKO $N$ NE SLISHKOM VELIKO.

oPISANNYJ METOD TREBUET $N-1$ SRAVNENIJ KAZHDYJ RAZ, KOGDA VYBIRAETSYA 
OCHEREDNAYA ZAPISX; ON TAKZHE TREBUET OTDELXNOJ OBLASTI VYVODA V PAMYATI. 
iMEETSYA OCHEVIDNYJ SPOSOB NESKOLXKO POPRAVITX SITUACIYU, IZBEZHAV PRI |TOM 
ISPOLXZOVANIYA $\infty$: VYBRANNOE ZNACHENIE MOZHNO ZAPISYVATX V 
SOOTVETSTVUYUSHCHUYU POZICIYU, A ZAPISX, KOTORAYA EE ZANIMALA, PERENOSITX 
NA MESTO VYBRANNOJ. tOGDA |TU POZICIYU NE NUZHNO RASSMATRIVATX VNOVX PRI 
POSLEDUYUSHCHIH VYBORAH. nA |TOJ IDEE OSNOVAN NASH PERVYJ ALGORITM SORTIROVKI 
POSREDSTVOM VYBORA.

\alg S.(sORTIROVKA POSREDSTVOM PROSTOGO VYBORA.) zAPISI $R_1$, \dots, 
$R_N$ PERERAZMESHCHAYUTSYA NA TOM ZHE MESTE. pOSLE ZAVERSHENIYA SORTIROVKI IH 
KLYUCHI BUDUT UPORYADOCHENY: $K_1\le \ldots\le K_N$. sORTIROVKA OSNOVANA NA 
OPISANNOM VYSHE METODE, ESLI NE SCHITATX TOGO, CHTO BOLEE, UDOBNO, 
OKAZYVAETSYA, VYBIRATX SNACHALA \emph{NAIBOLXSHIJ} |LEMENT, ZATEM VTOROJ PO 
VELICHINE I T. D.

\st[cIKL PO $j$.] vYPOLNITX SHAGI \stp{2} I \stp{3} PRI $j=N$, $N-1$, \dots,
  2.
%% 170 
\algend
\bye