\input style \chapnotrue \chapno=5 \subchno=2 \subsubchno=2 \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 \st[nAJTI~$\max(K_1,~\ldots, K_j)$.] nAJTI NAIBOLXSHIJ IZ KLYUCHEJ~$K_j$, $K_{j-1}$,~\dots, $K_1$; PUSTX |TO BUDET~$K_i$. \st[pOMENYATX MESTAMI S~$R_j$.] vZAIMOZAMENITX ZAPISI~$R_i\xchg R_j$. (tEPERX ZAPISI~$R_j$,~\dots, $R_N$ ZANIMAYUT SVOI OKONCHATELXNYE POZICII.) \algend \picture{rIS. ~21. sORTIROVKA PROSTYM VYBOROM.} v TABL.~1 POKAZANO DEJSTVIE |TOGO ALGORITMA NA SHESTNADCATX KLYUCHEJ, VYBRANNYH NAMI DLYA PRIMEROV; |LEMENTY, PRETENDUYUSHCHIE NA TO, CHTOBY OKAZATXSYA MAKSIMALXNYMI VO VREMYA POISKA V SHAGE~S2, VYDELENY ZHIRNYM SHRIFTOM. {\catcode`\!=\active\def!#1.{{\bf #1}} \htable{tABLICA 1}% {sORTIROVKA POSREDSTVOM PROSTOGO VYBORA}% {\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 }} sOOTVETSTVUYUSHCHAYA \MIX-PROGRAMMA DOVOLXNO PROSTA. \prog S.(sORTIROVKA POSREDSTVOM PROSTOGO VYBORA.) kAK I V PREDYDUSHCHIH PROGRAMMAH |TOJ GLAVY, ZAPISI, NAHODYASHCHIESYA V YACHEJKAH OT~$|INPUT|+1$ DO~$|INPUT|+N$, SORTIRUYUTSYA NA TOM ZHE MESTE PO KLYUCHU, ZANIMAYUSHCHEMU POLNOE SLOVO. zNACHENIYA REGISTROV: $|rA|\equiv \hbox{TEKUSHCHIJ MAKSIMUM}$, $|rI1|\equiv j-1$, $|rI2|\equiv k$ (INDEKS PRI POISKE), $|rI3|\equiv i$. pREDPOLAGAETSYA, CHTO~$N\ge 2$. \code START & ENT1 & N-1 & 1 & S1. cIKL PO~$j$. $j\asg N$. 2H & ENT2 & 0,1 & N-1 & S2. nAJTI~$\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 & pEREHOD, ESLI~$K_i\ge K_k$. & ENT3 & 0,2 & B & v PROTIVNOM SLUCHAE USTANOVITX~$i\asg k$, %% 171 & LDA & INPUT, 3 & B & $|rA|\asg K_i$. & DEC2 & 1 & A & $k\asg k-1$. & J2P & 8B & A & pOVTORITX, ESLI~$k>0$. & LDX & INPUT+1,1& N-1 & S3. pOMENYATX MESTAMI S~$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 vREMYA RABOTY |TOJ PROGRAMMY ZAVISIT OT CHISLA |LEMENTOV~$N$, CHISLA SRAVNENIJ~$A$ I CHISLA "PRAVOSTORONNIH MAKSIMUMOV"~$B$. nETRUDNO VIDETX, CHTO NEZAVISIMO OT ZNACHENIJ ISHODNYH KLYUCHEJ $$ A=\perm{N}{2}={1\over 2}N(N-1). \eqno(1) $$ sLEDOVATELXNO, PEREMENNOJ YAVLYAETSYA TOLXKO VELICHINA~$B$. nESMOTRYA NA VSYU BEZYSKUSNOSTX PROSTOGO VYBORA, NE TAK LEGKO PROIZVESTI TOCHNYJ ANALIZ VELICHINY~$B$. v UPR. S~3 PO~6 POKAZANO, CHTO $$ B=(\min 0, \ave (N+1)H_n-2N, \max \floor{N^2/4}); \eqno(2) $$ V |TOM SLUCHAE OSOBENNO INTERESNYM OKAZYVAETSYA MAKSIMALXNOE ZNACHENIE (STANDARTNOE OTKLONENIE VELICHINY~$B$ DO SIH POR NE OPREDELENO). tAKIM OBRAZOM, SREDNEE VREMYA RABOTY PROGRAMMY~S RAVNO $2.5N^2+3(N+1)H_N+3.5N-11$~EDINIC, T.~E.\ ONA LISHX NEMNOGIM MEDLENNEE PROSTYH VSTAVOK (PROGRAMMA~5.2.1S). iNTERESNO SRAVNITX ALGORITM~S S SORTIROVKOJ METODOM PUZYRXKA (ALGORITM~5.2.2v), TAK KAK METOD PUZYRXKA MOZHNO RASSMATRIVATX KAK ALGORITM VYBORA, V KOTOROM INOGDA VYBIRAETSYA BOLEE ODNOGO |LEMENTA ZA RAZ. pO |TOJ PRICHINE PRI SORTIROVKE METODOM PUZYRXKA PROIZVODITSYA MENXSHE SRAVNENIJ, CHEM PRI PROSTOM VYBORE, I ONA, KAK MOZHET POKAZATXSYA, PREDPOCHTITELXNEE. nO V DEJSTVITELXNOSTI PROGRAMMA~5.2.2v BOLEE CHEM VDVOE MEDLENNEE PROGRAMMY~S! sORTIROVKA METODOM PUZYRXKA PROIGRYVAET IZ-ZA TOGO, CHTO V NEJ VYPOLNYAETSYA SLISHKOM MNOGO OBMENOV, V TO VREMYA KAK PRI SORTIROVKE PROSTYM VYBOROM PROIZVODITSYA OCHENX MALO PERESYLOK DANNYH. \section uSOVERSHENSTVOVANIYA PROSTOGO VYBORA. sUSHCHESTVUET LI KAKOJ-NIBUDX SPOSOB ULUCHSHITX METOD VYBORA, ISPOLXZUEMYJ V ALGORITME~S? vOZXMEM K PRIMERU POISK MAKSIMUMA V SHAGE~S2: VOZMOZHEN LI SUSHCHESTVENNO BOLEE BYSTRYJ SPOSOB NAHOZHDENIYA MAKSIMUMA? oTVET NA |TOT VOPROS---\emph{NET!} \proclaim lEMMA~M. v LYUBOM ALGORITME NAHOZHDENIYA MAKSIMUMA IZ $n$~|LEMENTOV, OSNOVANNOM NA SRAVNENII PAR |LEMENTOV, NEOBHODIMO VYPOLNITX PO KRAJNEJ MERE $n-1$~SRAVNENIJ. %%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\rfloor1$, 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}r$, TO PEREJTI K SHAGU \stp{8}. \st[nAJTI "BOLXSHEGO" SYNA.] eSLI $K_j