\input style
%%172 
\proof eSLI PROIZVEDENO MENEE $n-1$ SRAVNENIJ, TO NAJDUTSYA PO KRAJNEJ MERE 
DVA |LEMENTA, DLYA KOTORYH NE BYLO OBNARUZHENO NI ODNOGO |LEMENTA, 
PREVOSHODYASHCHEGO IH PO VELICHINE. sLEDOVATELXNO, MY TAK I NE UZNAEM, 
KOTORYJ IZ |TIH DVUH |LEMENTOV BOLXSHE, I, ZNACHIT, NE SMOZHEM OPREDELITX MAKSIMUM.
\proofend

tAKIM OBRAZOM, PROCESS VYBORA, V KOTOROM OTYSKIVAETSYA NAIBOLXSHIJ |LEMENT, 
DOLZHEN SOSTOYATX NE MENEE CHEM IZ $n-1$ SHAGOV. oZNACHAET LI |TO, CHTO DLYA VSEH 
METODOV SORTIROVKI, OSNOVANNYH NA $n$ POVTORNYH VYBORAH, CHISLO SHAGOV 
NEIZBEZHNO BUDET PORYADKA $n^2$? k SCHASTXYU, LEMMA M PRIMENIMA TOLXKO K 
\emph{PERVOMU} SHAGU VYBORA; PRI POSLEDUYUSHCHIH VYBORAH MOZHNO 
ISPOLXZOVATX IZVLECHENNUYU RANEE INFORMACIYU. nAPRIMER, V UPR.~8 POKAZANO,
 CHTO SRAVNITELXNO PROSTOE IZMENENIE ALGORITMA~S NAPOLOVINU SOKRASHCHAET CHISLO SRAVNENIJ.

rASSMOTRIM 16 CHISEL, PREDSTAVLENNYH V 1-J STROKE V TABL.~1. oDIN IZ 
SPOSOBOV S|KONOMITX VREMYA PRI POSLEDUYUSHCHIH 
VYBORAH---RAZBITX VSE CHISLA NA CHETYRE GRUPPY PO CHETYRE CHISLA. nACHATX MOZHNO S 
OPREDELENIYA NAIBOLXSHEGO, |LEMENTA KAZHDOJ GRUPPY, A IMENNO SOOTVETSTVENNO S KLYUCHEJ
$$
512, 908, 653, 765;
$$
TOGDA NAIBOLXSHIJ IZ |TIH CHETYREH |LEMENTOV 908 I BUDET NAIBOLXSHIM VO 
VSEM FAJLE. chTOBY POLUCHITX VTOROJ PO VELICHINE |LEMENT, DOSTATOCHNO 
PROSMOTRETX SNACHALA OSTALXNYE TRI |LEMENTA GRUPPY, SODERZHASHCHEJ 908; 
NAIBOLXSHIJ IZ $\{170, 897, 275\}$ RAVEN 897, I TOGDA NAIBOLXSHIJ SREDI
$$
512, 897, 653, 765
$$
|TO 897. aNALOGICHNO, DLYA TOGO CHTOBY POLUCHITX TRETIJ PO VELICHINE |LEMENT, 
OPREDELYAEM NAIBOLXSHIJ IZ $\{170, 275\}$, A ZATEM NAIBOLXSHIJ IZ
$$
512, 275, 653, 765
$$
I T. D. kAZHDYJ VYBOR, KROME PERVOGO, TREBUET NE BOLEE 6 DOPOLNITELXNYH 
SRAVNENIJ. vOOBSHCHE, ESLI $N$---TOCHNYJ KVADRAT, TO MOZHNO RAZDELITX FAJL NA 
$\sqrt N$ GRUPP PO $\sqrt N$ |LEMENTOV V KAZHDOJ;
LYUBOJ VYBOR, KROME PERVOGO, TREBUET NE BOLEE CHEM $\sqrt{N}-1$ SRAVNENIJ 
VNUTRI GRUPPY RANEE VYBRANNOGO |LEMENTA PLYUS $\sqrt{N}-1$ SRAVNENIJ SREDI 
"LIDEROV GRUPP". eTOT METOD POLUCHIL NAZVANIE "KVADRATICHNYJ VYBOR"; OBSHCHEE 
VREMYA RABOTY DLYA NEGO ESTX $O(N\sqrt{N})$, CHTO SUSHCHESTVENNO LUCHSHE, CHEM $O(N^2)$.

mETOD KVADRATICHNOGO VYBORA VPERVYE OPUBLIKOVAN 
e.~X.~fR|NDOM [{\sl JACM\/}, {\bf 3} (1956), 152--154]; ON UKAZAL, CHTO |TU 
IDEYU MOZHNO .OBOBSHCHITX, POLUCHIV V REZULXTATE METOD KUBICHESKOGO VYBORA, 
VYBORA CHETVERTOJ STEPENI I T. D. nAPRIMER, METOD KUBICHESKOGO
%%173
VYBORA SOSTOIT V TOM, CHTOBY RAZDELITX FAJL NA $\root 3\of N$ BOLXSHIH GRUPP,
 KAZHDAYA IZ KOTORYH SODERZHIT PO $\root 3\of N$ MALYH GRUPP PO $\root 3\of 
N$ ZAPISEJ; VREMYA RABOTY PROPORCIONALXNO $N\root 3\of N$. eSLI RAZVITX 
|TU IDEYU DO EE POLNOGO ZAVERSHENIYA, TO MY PRIDEM K TOMU, CHTO fR|ND NAZVAL 
"VYBOR $n$-J STEPENI", OSNOVANNYJ NA STRUKTURE BINARNOGO DEREVA. vREMYA 
RABOTY |TOGO METODA PROPORCIONALXNO $N \log N$; MY BUDEM NAZYVATX EGO 
\dfn{VYBOROM IZ DEREVA}.
\section vYBOR IZ DEREVA. pRINCIPY SORTIROVKI POSREDSTVOM VYBORA IZ DEREVA 
BUDET LEGCHE VOSPRINYATX, ESLI VOSPOLXZOVATXSYA ANALOGIEJ S TIPICHNYM 
"TURNIROM S VYBYVANIEM". rASSMOTRIM, NAPRIMER, REZULXTATY SOREVNOVANIYA 
PO NASTOLXNOMU TENNISU, POKAZANNYE NA RIS.~22. dZHIM POBEZHDAET dONA, A 
dZHO POBEZHDAET dZHEKA; ZATEM V SLEDUYUSHCHEM TURE dZHO VYIGRYVAET U dZHIMA I T. D.

nA RIS.~22 POKAZANO, CHTO dZHO---CHEMPION SREDI VOSXMI SPORTSMENOV, A DLYA 
TOGO, CHTOBY OPREDELITX |TO, POTREBOVALOSX $8-1=7$ MATCHEJ (T. E. SRAVNENIJ).
 dIK VOVSE NE OBYAZATELXNO BUDET VTORYM PO SILE IGROKOM: LYUBOJ IZ 
SPORTSMENOV, U KOTORYH VYIGRAL dZHO, VKLYUCHAYA DAZHE PROIGRAVSHEGO V PERVOM 
TURE dZHEKA, MOG BY OKAZATXSYA VTORYM PO SILE IGROKOM. vTOROGO IGROKA MOZHNO 
OPREDELITX, ZASTAVIV dZHEKA SYGRATX S dZHIMOM, A POBEDITELYA |TOGO MATCHA---S 
dIKOM; VSEGO DVA DOPOLNITELXNYH MATCHA TREBUETSYA DLYA OPREDELENIYA VTOROGO PO 
SILE IGROKA, ISHODYA IZ TOGO SOOTNOSHENIYA SIL, KOTOROE MY ZAPOMNILI IZ 
PREDYDUSHCHIH IGR.

vOOBSHCHE MOZHNO "VYVESTI" IGROKA, NAHODYASHCHEGOSYA V KORNE DEREVA, I ZAMENITX EGO 
CHREZVYCHAJNO SLABYM IGROKOM. pODSTANOVKA |TOGO SLABOGO IGROKA OZNACHAET, 
CHTO PERVONACHALXNO VTOROJ PO SILE SPORTSMEN STANET TEPERX NAILUCHSHIM, I 
IMENNO ON OKAZHETSYA V KORNE, ESLI VNOVX VYCHISLITX POBEDITELEJ V 
VERHNIH UROVNYAH DEREVA. dLYA |TOGO NUZHNO IZMENITX LISHX ODIN PUTX, V DEREVE, 
TAK CHTO DLYA VYBORA SLEDUYUSHCHEGO PO SILE IGROKA NEOBHODIMO MENEE $\lceil 
\log_2 N\rceil$) DOPOLNITELXNYH SRAVNENIJ. sUMMARNOE
%%174
\picture{rIS. 23. pRIMER SORTIROVKI POSREDSTVOM VYBORA IZ DEREVA...}
%% 175
VREMYA VYPOLNENIYA TAKOJ SORTIROVKI POSREDSTVOM VYBORA PRIMERNO 
PROPORCIONALXNO $N\log N$.

nA RIS.~23 SORTIROVKE POSREDSTVOM VYBORA IZ DEREVA PODVERGAYUTSYA NASHI 16 
CHISEL. zAMETIM, CHTO DLYA TOGO, CHTOBY ZNATX, KUDA VSTAVLYATX SLEDUYUSHCHIJ 
|LEMENT "$-\infty$", NEOBHODIMO POMNITX, OTKUDA PRISHEL KLYUCH, NAHODYASHCHIJSYA V 
KORNE. pO|TOMU UZLY RAZVETVLENIYA V DEJSTVITELXNOSTI SODERZHAT UKAZATELI 
ILI INDEKSY, OPISYVAYUSHCHIE POZICIYU KLYUCHA, A NE SAM KLYUCH. oTSYUDA SLEDUET, CHTO 
NEOBHODIMA PAMYATX DLYA $N$ ISHODNYH ZAPISEJ, $N-1$ SLOV-UKAZATELEJ I $N$ 
VYVODIMYH ZAPISEJ. (rAZUMEETSYA, ESLI VYVOD
\picture{rIS. 24.  pRIMENENIE KORPORATIVNOJ SISTEMY VYDVIZHENIJ K 
SORTIROVKE. kAZHDYJ PODNIMAETSYA NA SVOJ UROVENX NEKOMPETENTNOSTI V IERARHII.}
IDET NA LENTU ILI NA DISK, TO NE NUZHNO SOHRANYATX VYVODIMYE ZAPISI V 
OPERATIVNOJ PAMYATI.)

chTOBY OCENITX TE ZAMECHATELXNYE USOVERSHENSTVOVANIYA, KOTORYE MY SOBIRAEMSYA 
OBSUDITX, V |TOM MESTE SLEDUET PRERVATX CHTENIE DO TEH POR, POKA VY NE 
OSVOITESX S VYBOROM IZ DEREVA HOTYA BY NASTOLXKO, CHTO RESHENIE UPR.~10 NE 
SOSTAVIT DLYA VAS NIKAKOGO TRUDA.

oDNA IZ MODIFIKACIJ VYBORA IZ DEREVA, VVEDENNAYA, PO SUSHCHESTVU, 
k.~e.~aJVERSONOM [A Programming Language (Wiley, 1962), 223--227], 
USTRANYAET NEOBHODIMOSTX UKAZATELEJ, SLEDUYUSHCHIM OBRAZOM OSUSHCHESTVLYAYA 
"ZAGLYADYVANIE VPERED": KOGDA POBEDITELX MATCHA NA NIZHNEM UROVNE PODNIMAETSYA 
VVERH, TO NA NIZHNEM UROVNE EGO SRAZU ZHE MOZHNO ZAMENITX NA "$-\infty$"; 
KOGDA ZHE POBEDITELX PEREMESHCHAETSYA VVERH S ODNOGO RAZVETVLENIYA NA DRUGOE,
 TO EGO MOZHNO ZAMENITX IGROKOM, KOTORYJ V KONCE KONCOV VSE RAVNO DOLZHEN 
PODNYATXSYA, NA EGO PREZHNEE MESTO (A IMENNO NAIBOLXSHIM IZ DVUH KLYUCHEJ, 
RASPOLOZHENNYH POD NIM). vYPOLNIV |TU OPERACIYU STOLXKO RAZ, SKOLXKO 
VOZMOZHNO, PRIDEM OT RIS.~23(A) K RIS.~24.

kOLX SKORO DEREVO POSTROENO TAKIM OBRAZOM, MOZHNO PRODOLZHATX SORTIROVKU 
NE "VOSHODYASHCHIM" METODOM, POKAZANNYM NA RIS.~23, A "NISHODYASHCHIM": VYVODITSYA 
|LEMENT, NAHODYASHCHIJSYA
%% 176
V KORNE, PEREMESHCHAETSYA VVERH NAIBOLXSHIJ IZ EGO POTOMKOV, PEREMESHCHAETSYA VVERH 
NAIBOLXSHIJ IZ POTOMKOV POSLEDNEGO I T. D. pROCESS NACHINAET POHODITX NE 
STOLXKO NA TURNIR PO NASTOLXNOMU TENNISU, SKOLXKO NA KORPORATIVNUYU SISTEMU VYDVIZHENIJ.

chITATELX DOLZHEN UYASNITX, CHTO U NISHODYASHCHEGO METODA ESTX VAZHNOE 
DOSTOINSTVO---ON POZVOLYAET IZBEZHATX LISHNIH SRAVNENIJ $-\infty$ S~$-\infty$. 
(pOLXZUYASX VOSHODYASHCHIM METODOM, MY NA BOLEE POZDNIH STADIYAH SORTIROVKI 
VSYUDU NATYKAEMSYA NA $-\infty$, A PRI NISHODYASHCHEM METODE MOZHNO NA KAZHDOJ 
STADII ZAKANCHIVATX PREOBRAZOVANIE DEREVA SRAZU ZHE POSLE ZANESENIYA $-\infty$.)
\picture{rIS. 25. pOSLEDOVATELXNOE RASPREDELENIE PAMYATI DLYA 
POLNOGO BINARNOGO DEREVA.}

nA RIS.~23 I~24 IZOBRAZHENY \emph{POLNYE BINARNYE DEREVXYA} S 16 KONCEVYMI 
UZLAMI (SR. S P.~2.3.4.5); TAKIE DEREVXYA UDOBNO HRANITX V 
POSLEDOVATELXNYH YACHEJKAH PAMYATI, KAK POKAZANO NA RIS.~25. zAMETIM, CHTO 
OTCOM UZLA NOMER $k$ YAVLYAETSYA UZEL $\lfloor k/2\rfloor$ , A EGO POTOMKAMI 
YAVLYAYUTSYA UZLY $2k$ I $2k+1$. oTSYUDA VYTEKAET ESHCHE ODNO PREIMUSHCHESTVO 
NISHODYASHCHEGO METODA, POSKOLXKU ZACHASTUYU ZNACHITELXNO PROSHCHE PRODVIGATXSYA VNIZ 
OT UZLA $k$ K UZLAM $2k$ I~$2k+1$, CHEM VVERH OT UZLA $k$ K UZLAM $k\oplus 
1$ 
I~$\lfloor k/2\rfloor$. (zDESX CHEREZ $k\oplus 1$ OBOZNACHENO CHISLO $k+1$ 
ILI $k-1$ V ZAVISIMOSTI OT  TOGO, YAVLYAETSYA LI $k$ CHETNYM ILI NECHETNYM.)

dO SIH POR V NASHIH PRIMERAH VYBORA IZ DEREVA V TOJ ILI INOJ MERE 
PREDPOLAGALOSX, CHTO $N$ ESTX STEPENX 2; V DEJSTVITELXNOSTI MOZHNO 
RABOTATX S PROIZVOLXNYM ZNACHENIEM $N$, TAK KAK POLNOE BINARNOE DEREVO S 
$N$ KONCEVYMI UZLAMI NETRUDNO POSTROITX DLYA LYUBOGO N. 

 mY PODOSHLI TEPERX K OSNOVNOMU VOPROSU: NELXZYA LI V NISHODYASHCHEM METODE 
OBOJTISX SOVSEM BEZ "$-\infty$"? nE PRAVDA LI, BYLO BY CHUDESNO, ESLI BY 
VSYU SUSHCHESTVENNUYU INFORMACIYU, IMEYUSHCHUYUSYA NA RIS.~24, UDALOSX RASPOLOZHITX V 
YACHEJKAH 1--16
%%177
POLNOGO BINARNOGO DEREVA BEZ VSYAKIH BESPOLEZNYH "DYR", SODERZHASHCHIH 
$-\infty$? pORAZMYSLIV, MOZHNO PRIJTI K VYVODU, CHTO |TA CELX V 
DEJSTVITELXNOSTI DOSTIZHIMA, PRICHEM NE TOLXKO ISKLYUCHAETSYA $-\infty$, NO I 
POYAVLYAETSYA VOZMOZHNOSTX SORTIROVATX $N$ ZAPISEJ NA TOM ZHE MESTE BEZ 
VSPOMOGATELXNOJ OBLASTI VYVODA. eTO PRIVODIT K ESHCHE ODNOMU VAZHNOMU 
ALGORITMU SORTIROVKI. eGO AVTOR dZH.~u.~dZH.~uILXYAMS [{\sl CACM\/}, {\bf 7} 
(1964), 347--348] OKRESTIL SVOJ ALGORITM "PIRAMIDALXNOJ-SORTIROVKOJ" ("heapsort").

\section pIRAMIDALXNAYA SORTIROVKA.  bUDEM NAZYVATX FAJL KLYUCHEJ $K_1$, 
$K_2$, \dots, $K_N$ "PIRAMIDOJ", ESLI
$$
K_{\lfloor j/2\rfloor}\ge K_j \rem{ PRI $1\le \lfloor j/2\rfloor<j\le N$.}
\eqno(3)
$$
v |TOM SLUCHAE $K_1\ge K_2$, $K_1\ge K_3$, $K_2\ge K_4$ I T.D.; IMENNO |TO 
USLOVIE VYPOLNYAETSYA NA RIS.~24. iZ NEGO SLEDUET, V CHASTNOSTI, CHTO 
NAIBOLXSHIJ KLYUCH OKAZYVAETSYA "NA VERSHINE PIRAMIDY":
$$
K_1=\max(K_1, K_2, \ldots, K_N).
\eqno(4)
$$
eSLI BY MY SUMELI KAK-NIBUDX PREOBRAZOVATX PROIZVOLXNYJ ISHODNYJ FAJL V 
PIRAMIDU, TO DLYA POLUCHENIYA |FFEKTIVNOGO ALGORITMA SORTIROVKI MOZHNO BYLO BY 
VOSPOLXZOVATXSYA "NISHODYASHCHEJ" PROCEDUROJ VYBORA, PODOBNOJ TOJ, KOTORAYA 
OPISANA VYSHE.

eFFEKTIVNYJ PODHOD K ZADACHE POSTROENIYA PIRAMIDY PREDLOZHIL r.~u.~fLOJD 
[{\sl CACM\/}, {\bf 7} (1964), 701]. pUSTX NAM UDALOSX RASPOLOZHITX FAJL 
TAKIM OBRAZOM, CHTO
$$
K_{\lfloor j/2\rfloor}\ge K_j \rem{ PRI $l < \lfloor j/2\rfloor<j\le N$,}
\eqno(5)
$$
GDE $l$---NEKOTOROE CHISLO $\ge1$. (v ISHODNOM FAJLE |TO USLOVIE VYPOLNYAETSYA 
"AVTOMATICHESKI" DLYA $l=\floor{N/2}$, POSKOLXKU NI ODIN INDEKS $j$ NE 
UDOVLETVORYAET USLOVIYU $\floor{N/2}<\floor{j/2}<j\le N$.) 
nETRUDNO PONYATX, KAK, IZMENYAYA LISHX PODDEREVO S KORNEM V UZLE $l$, 
PREOBRAZOVATX FAJL, CHTOBY RASPROSTRANITX NERAVENSTVA (5) I NA SLUCHAJ, 
KOGDA $\floor{j/2}=l$. sLEDOVATELXNO, MOZHNO UMENXSHATX $l$ NA EDINICU, POKA V 
KONCE KONCOV NE BUDET DOSTIGNUTO USLOVIE (3). eTI IDEI uILXYAMSA I fLOJDA 
PRIVODYAT K IZYASHCHNOMU ALGORITMU, KOTORYJ ZASLUZHIVAET PRISTALXNOGO IZUCHENIYA.

\alg H.(pIRAMIDALXNAYA SORTIROVKA.) 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$. sNACHALA 
FAJL PERESTRAIVAETSYA V PIRAMIDU, POSLE CHEGO VERSHINA PIRAMIDY MNOGOKRATNO 
ISKLYUCHAETSYA I ZAPISYVAETSYA NA SVOE OKONCHATELXNOE MESTO. pREDPOLAGAETSYA, 
CHTO $N\ge2$.
\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $l\asg\floor{N/2}+1$, $r\asg N$.
\st[uMENXSHITX $l$ ILI~$r$.] eSLI. $l>1$, TO USTANOVITX $l\asg l-1$, $R\asg 
R_l$, $K\asg K_l$. (eSLI  $l>1$, |TO OZNACHAET, CHTO PROISHODIT
%% 178
PROCESS PREOBRAZOVANIYA ISHODNOGO FAJLA V PIRAMIDU; ESLI ZHE $l= 1$, TO |TO 
ZNACHIT, CHTO KLYUCHI $K_1$, $K_2$, \dots, $K_r$ UZHE OBRAZUYUT PIRAMIDU.) v 
PROTIVNOM SLUCHAE USTANOVITX $R\asg R_r$, $K\asg K_r$, $R_r\asg R_1$  I 
$r\asg r-1$; ESLI V REZULXTATE OKAZALOSX, CHTO $r=1$, TO USTANOVITX 
$R_1\asg R$ I ZAVERSHITX RABOTU ALGORITMA.

\st[pRIGOTOVITXSYA K "PROTASKIVANIYU".] uSTANOVITX $j\asg l$. 
(k |TOMU MOMENTU
$$
K_\floor{j/2}\ge K_j \rem{PRI $l<\floor{j/2}<j\le r$,}
\eqno(6)
$$
A ZAPISI $R_k$, $r<k\le N$, ZANIMAYUT SVOI OKONCHATELXNYE MESTA. shAGI 
\stp{3}--\stp{8} NAZYVAYUTSYA ALGORITMOM "PROTASKIVANIYA"; IH
\picture{rIS. 26. pIRAMIDALXNAYA SORTIROVKA; PUNKTIROM OBVEDEN ALGORITM "PROTASKIVANIYA".}
DEJSTVIE |KVIVALENTNO USTANOVKE $R_l\asg R$ S POSLEDUYUSHCHIM PEREMESHCHENIEM 
ZAPISEJ $R_l$, \dots, $R_r$ TAKIM OBRAZOM, CHTOBY USLOVIE (6) VYPOLNYALOSX I 
PRI $\floor{j/2}=l$.)

\st[pRODVINUTXSYA VNIZ.] uSTANOVITX $i\asg j$ I $j\asg 2j$. (v POSLEDUYUSHCHIH 
SHAGAH $i = \floor{j/2}$.) eSLI $j< r$, TO PEREJTI K SHAGU \stp{5};
ESLI $j=r$, TO PEREJTI K SHAGU \stp{6}; ESLI ZHE $j>r$, TO PEREJTI K SHAGU \stp{8}.

\st[nAJTI "BOLXSHEGO" SYNA.] eSLI $K_j<K_{j+1}$, TO USTANOVITX
$j\asg j+1$.

\st[bOLXSHE $K$?] eSLI $K\ge K_j$, TO PEREJTI K SHAGU \stp{8}. 
\st[pODNYATX EGO VVERH.] uSTANOVITX $R_i\asg R_j$ I VOZVRATITXSYA
K SHAGU \stp{4}.

\st[zANESTI $R$.] uSTANOVITX $R_i\asg R$. (nA |TOM ALGORITM 
"PROTASKIVANIYA", NACHATYJ V SHAGE \stp{z}, ZAKANCHIVAETSYA.) vOZVRATITXSYA 
K SHAGU \stp{2}.
\algend
%%179
\bye



