\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\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