\input style %%150 DLYA SORTIROVKI) BYSTRAYA SORTIROVKA PREVRASHCHAETSYA V OTNYUDX NE BYSTRUYU. vREMYA EE RABOTY STANOVITSYA PROPORCIONALXNYM $N^2$, A NE $N\log N$ (SM. UPR.~25). v OTLICHIE OT DRUGIH ALGORITMOV SORTIROVKI, KOTORYE NAM VSTRECHALISX, ALGORITM Q PREDPOCHITAET NEUPORYADOCHENNYE FAJLY! v UPOMYANUTOJ STATXE hOARA PREDLOZHENY DVA SPOSOBA POPRAVITX SITUACIYU, OSNOVYVAYUSHCHIHSYA NA VYBORE LUCHSHEGO ZNACHENIYA PROVERYAEMOGO KLYUCHA $K$, KOTORYJ UPRAVLYAET RAZDELENIEM. oDNA IZ EGO REKOMENDACIJ SOSTOIT .V TOM, CHTOBY V POSLEDNEJ CHASTI SHAGA Q2 VYBIRATX \emph{SLUCHAJNOE} CELOE CHISLO $q$ MEZHDU $l$ I~$r$; V |TOM SHAGE MOZHNO ZAMENITX INSTRUKCII "$K\asg K_l$, $R\asg R_l$" NA $$ K\asg K_q, \quad R\asg R_q, \quad R_q\asg R_l. \eqno(27) $$ sOGLASNO FORMULAM (25), TAKIE SLUCHAJNYE CELYE CHISLA PRIDETSYA VYCHISLYATX V SREDNEM LISHX $2(N+1)/(M+2)-1$~RAZ, TAK CHTO DOPOLNITELXNOE VREMYA RABOTY NESUSHCHESTVENNO, A SLUCHAJNYJ VYBOR---HOROSHAYA ZASHCHITA OT OPASNOSTI OKAZATXSYA V NAIHUDSHEJ SITUACII. vTOROE PREDLOZHENIE hOARA SOSTOIT V TOM, CHTOBY PROSMOTRETX NEBOLXSHOJ UCHASTOK FAJLA I NAJTI MEDIANU DLYA |TOJ SOVOKUPNOSTI DANNYH. tAKOMU PODHODU POSLEDOVAL r. k. sINGLTON [{\sl CACM\/}, {\bf 12} (1969), 185--187], KOTORYJ PREDLOZHIL V KACHESTVE $K_q$ BRATX MEDIANU TREH ZNACHENIJ $$ K_l, \quad K_{\lfloor(l+r)/2\rfloor}, \quad K_r. \eqno(28) $$ pROCEDURA sINGLTONA SOKRASHCHAET CHISLO SRAVNENIJ S $2N \ln N$ PRIMERNO DO ${12\over7}N\ln N$ (SM. UPR. 29). mOZHNO POKAZATX, CHTO. V |TOM SLUCHAE $B_N$ ASIMPTOTICHESKI PRIBLIZHAETSYA K $C_N/5$, A NE K~$C_N/6$, TAK CHTO METOD MEDIANY NESKOLXKO UVELICHIVAET VREMYA, ZATRACHIVAEMOE NA PERESYLKU DANNYH, PO|TOMU OBSHCHEE VREMYA RABOTY SOKRASHCHAETSYA PRIMERNO, NA 8\%. (pODROBNYJ ANALIZ SM. V UPR.56.) vREMYA RABOTY V NAIHUDSHEM SLUCHAE VSE ESHCHE PORYADKA $N^2$, ODNAKO S TAKIM MEDLENNYM POVEDENIEM ALGORITMA VRYAD LI KOGDA-LIBO PRIDETSYA VSTRETITXSYA NA PRAKTIKE. u.~d.~fR|JZER I a.~ch.~mAK-kELLAR [{\sl JACM\/}, {\bf 17} (1970), 496--507] PREDLOZHILI RASSMATRIVATX SOVOKUPNOSTX GORAZDO BOLXSHEGO OB®EMA IZ $2^k-1$ ZAPISEJ, GDE $k$ VYBIRAETSYA TAK, CHTOBY $2^k\approx N/\ln N$. eTU SOVOKUPNOSTX MOZHNO OTSORTIROVATX OBYCHNYM METODOM BYSTROJ SORTIROVKI, POSLE CHEGO |LEMENTY VSTAVLYAYUTSYA SREDI OSTALXNYH ZAPISEJ ZA $k$ PROSMOTROV VSEGO FAJLA (V REZULXTATE FAJL BUDET RAZDELEN NA $2^k$ PODFAJLOV, OGRANICHENNYH |LEMENTAMI PERVONACHALXNOJ SOVOKUPNOSTI). nA ZAKLYUCHITELXNOM |TAPE SORTIRUYUTSYA POLUCHENNYE PODFAJLY. sREDNEE CHISLO, SRAVNENIJ, VYPOLNYAEMYH TAKOJ PROCEDUROJ "SORTIROVKI SOVOKUPNOSTI", PRIMERNO TAKOE ZHE, KAK I DLYA METODA MEDIANY sINGLTONA, KOGDA $N$ %%151 NAHODITSYA V PRAKTICHESKOM DIAPAZONE ZNACHENIJ, NO PRI $N\to\infty$ ONO ASIMPTOTICHESKI PRIBLIZHAETSYA K $N\log_2N$. \section oBMENNAYA PORAZRYADNAYA SORTIROVKA. mY PODHODIM TEPERX K METODU, SOVERSHENNO OTLICHNOMU OT VSEH SHEM SORTIROVKI, KOTORYE RASSMATRIVALISX PREZHDE; V NEM ISPOLXZUETSYA \emph{DVOICHNOE PREDSTAVLENIE} KLYUCHEJ, I.POTOMU ON PREDNAZNACHEN ISKLYUCHITELXNO DLYA DVOICHNYH MASHIN. vMESTO TOGO CHTOBY SRAVNIVATX MEZHDU SOBOJ DVA KLYUCHA, V |TOM METODE PROVERYAETSYA, RAVNY LI 0 ILI 1 OTDELXNYE BITY KLYUCHA. v DRUGIH OTNOSHENIYAH ON OBLADAET HARAKTERISTIKAMI OBMENNOJ SORTIROVKI I NA SAMOM DELE OCHENX NAPOMINAET BYSTRUYU SORTIROVKU. tAK KAK ON ZAVISIT OT RAZRYADOV KLYUCHA, PREDSTAVLENNOGO V DVOICHNOJ SISTEME SCHISLENIYA, MY NAZYVAEM EGO "OBMENNOJ PORAZRYADNOJ SORTIROVKOJ". v OBSHCHIH CHERTAH |TOT ALGORITM MOZHNO OPISATX SLEDUYUSHCHIM OBRAZOM: \enumerate \li pOSLEDOVATELXNOSTX SORTIRUETSYA \emph{PO STARSHEMU ZNACHASHCHEMU DVOICHNOMU BITU} TAK, CHTOBY VSE KLYUCHI, NACHINAYUSHCHIESYA S 0, OKAZALISX PERED VSEMI KLYUCHAMI, NACHINAYUSHCHIMISYA S 1. dLYA |TOGO NADO NAJTI SAMYJ LEVYJ KLYUCH $K_i$, NACHINAYUSHCHIJSYA S 1, I SAMYJ PRAVYJ KLYUCH $K_j$, NACHINAYUSHCHIJSYA S 0, POSLE CHEGO $R_i$ I $R_j$ MENYAYUTSYA MESTAMI, I PROCESS POVTORYAETSYA, POKA NE STANET $i>j$. \li pUSTX $F_0$---MNOZHESTVO |LEMENTOV, NACHINAYUSHCHIHSYA S 0, A $F_1$---VSE OSTALXNYE. pRIMENIM K $F_0$ PORAZRYADNUYU SORTIROVKU (NACHAV TEPERX SO \emph{VTOROGO} BITA SLEVA, A NE SO STARSHEGO) DO TEH POR, POKA MNOZHESTVO $F_0$ .NE BUDET POLNOSTXYU OTSORTIROVANO; ZATEM PRODELAEM TO ZHE S $F_1$. \enumend nAPRIMER, V TABL.~3 POKAZANO, KAK DEJSTVUET OBMENNAYA PORAZRYADNAYA SORTIROVKA NA NASHI 16 SLUCHAJNYH CHISEL, ZAPISANNYH TEPERX V VOSXMERICHNOJ SISTEME SCHISLENIYA. nA STADII 1 POKAZAN ISHODNYJ FAJL; POSLE OBMENOV PO PERVOMU BITU PRIHODIM KO VTOROJ STADII. nA VTOROJ STADII SORTIRUETSYA PERVAYA GRUPPA PO VTOROMU, BITU, NA TRETXEJ---PO TRETXEMU BITU. (chITATELX DOLZHEN MYSLENNO PREOBRAZOVATX VOSXMERICHNYE CHISLA V 10-RAZRYADNYE DVOICHNYE.) kOGDA MY POSLE SORTIROVKI PO .CHETVERTOMU BITU DOSTIGAEM PYATOJ STADII, TO OBNARUZHIVAEM, CHTO KAZHDAYA IZ OSTAVSHIHSYA GRUPP SODERZHIT VSEGO PO ODNOMU |LEMENTU,- TAK CHTO |TU CHASTX FAJLA MOZHNO BOLXSHE NE RASSMATRIVATX. zAPISX "${}^4[0232\ 0252]$" OZNACHAET, CHTO PODFAJL $0232\ 0252$ ESHCHE PREDSTOIT SORTIROVATX PO CHETVERTOMU BITU SLEVA. v |TOM KONKRETNOM SLUCHAE SORTIROVKA PO CHETVERTOMU BITU NE DAET NICHEGO NOVOGO; CHTOBY RAZDELITX |LEMENTY, NEOBHODIMO DOBRATXSYA DO PYATOGO BITA. vESX PROCESS SORTIROVKI, POKAZANNYJ V TABL.~3, VYPOLNYAETSYA ZA 22 STADII; |TO NESKOLXKO BOLXSHE SOOTVETSTVUYUSHCHEGO CHISLA V BYSTROJ SORTIROVKE (TABL.~2). chISLO PROVEROK BITOV 82 TAKZHE VELIKO; NO MY UVIDIM, CHTO CHISLO PROVEROK BITOV PRI BOLXSHIH 151 %%152 \picture{tABLICA 3} %%153 $N$ V DEJSTVITELXNOSTI MENXSHE, CHEM CHISLO SRAVNENIJ V BYSTROJ SORTIROVKE, V PREDPOLOZHENII O RAVNOMERNOM RASPREDELENII KLYUCHEJ. oBSHCHEE CHISLO OBMENOV V TABL.~3 RAVNO 17, T. E. VESXMA UMERENNO. zAMETIM, CHTO, HOTYA SORTIRUYUTSYA 10-BITOVYE CHISLA, V DANNOM PRIMERE PRI PROVERKE BITOV NIKOGDA NE PRIHODITSYA IDTI DALXSHE SEDXMOGO BITA. kAK I PRI BYSTROJ SORTIROVKE, DLYA HRANENIYA "INFORMACII O GRANICAH" PODFAJLOV, OZHIDAYUSHCHIH SORTIROVKI, MOZHNO VOSPOLXZOVATXSYA STEKOM. vMESTO TOGO CHTOBY SORTIROVATX V PERVUYU OCHEREDX NAIMENXSHIJ IZ PODFAJLOV, UDOBNO PROSTO PRODVIGATXSYA SLEVA NAPRAVO, TAK KAK RAZMER STEKA V. |TOM SLUCHAE NIKOGDA NE PREVZOJDET CHISLA BITOV V SORTIRUEMYH KLYUCHAH. v ALGORITME, PRIVEDENNOM NIZHE, |LEMENT STEKA $(r, b)$ UKAZYVAET NA TO, CHTO PODFAJL S PRAVOJ GRANICEJ $r$ OZHIDAET SORTIROVKI PO BITU $b$; LEVUYU GRANICU MOZHNO NE ZAPOMINATX V STEKE: ONA VSEGDA ZADANA NEYAVNO, POSKOLXKU V |TOJ PROCEDURE FAJL VSEGDA OBRABATYVAETSYA SLEVA NAPRAVO. \alg R.(oBMENNAYA PORAZRYADNAYA 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$. pREDPOLAGAETSYA, CHTO VSE KLYUCHI---$m$-RAZRYADNYE DVOICHNYE CHISLA $(a_1\ a_2\ \ldots\ a_m)_2$; $i$-J PO STARSHINSTVU BIT $a_i$ NAZYVAETSYA "BIT $i$" KLYUCHA. tREBUETSYA VSPOMOGATELXNYJ STEK, VMESHCHAYUSHCHIJ DO $m-1$ |LEMENTOV. eTOT ALGORITM, PO SUSHCHESTVU, SLEDUET PROCEDURE OBMENNOJ PORAZRYADNOJ SORTIROVKI S RAZDELENIYAMI, OPISANNOJ VYSHE; VOZMOZHNY NEKOTORYE USOVERSHENSTVOVANIYA S CELXYU POVYSHENIYA |FFEKTIVNOSTI (ONI OPISANY DALEE V TEKSTE I V UPRAZHNENIYAH). \st[nACHALXNAYA USTANOVKA.] oPUSTOSHITX STEK I USTANOVITX $l\asg 1$, $r\asg N$, $b\asg 1$. \st[nACHATX NOVUYU STADIYU.] (mY HOTELI BY TEPERX OTSORTIROVATX PODFAJL $R_l\le \ldots \le R_r$ PO BITU $b$; PO SMYSLU ALGORITMA $l\le r$.) eSLI $l=r$, TO PEREJTI K SHAGU \stp{10} (TAK KAK FAJL, SOSTOYASHCHIJ IZ ODNOGO SLOVA, UZHE OTSORTIROVAN). v PROTIVNOM SLUCHAE USTANOVITX $i\asg l$, $j\asg r$. \st[pROVERITX $K_i$ NA 1.] pROVERITX BIT $b$ KLYUCHA $K_i$.. eSLI ON RAVEN 1, TO PEREJTI K SHAGU \stp{6}. \st[uVELICHITX $i$.] uVELICHITX $i$ NA 1. eSLI $i\le j$, TO VOZVRATITXSYA K SHAGU \stp{3}; V PROTIVNOM SLUCHAE PEREJTI K SHAGU \stp{8}. \st[pROVERITX $K_{j+1}$ NA 0.] pROVERITX BIT $b$ KLYUCHA $K_{j+1}$. eSLI ON RAVEN 0, TO PEREJTI K SHAGU \stp{7}. \st[uMENXSHITX $j$.] uMENXSHITX $j$ NA 1. eSLI$ i\le j$, TO PEREJTI K SHAGU \stp{5}; V PROTIVNOM SLUCHAE PEREJTI K SHAGU \stp{8}. \st[pOMENYATX MESTAMI $R_i$, $R_{j+1}$]. pOMENYATX MESTAMI $R_i\xchg R_{j+1}$, ZATEM PEREJTI K SHAGU \stp{4}. \st[pROVERITX OSOBYE SLUCHAI.] (k |TOMU MOMENTU STADIYA RAZDELENIYA %%154 ZAVERSHENA, $i=j+1$, BIT $b$ KLYUCHEJ~$K_l$, \dots, $K_j$ RAVEN~$0$, A BIT~$b$ KLYUCHEJ $K_i$, \dots, $K_r$ RAVEN~$1$.) uVELICHITX $b$ NA~1. eSLI $b>m$, GDE $m$---OBSHCHEE CHISLO BITOV V KLYUCHAH, TO PEREJTI K SHAGU~\stp{10}. (eTO OZNACHAET, CHTO PODFAJL $R_l$ \dots $R_r$ OTSORTIROVAN. eSLI V FAJLE NE MOZHET BYTX RAVNYH KLYUCHEJ, TO TAKUYU PROVERKU MOZHNO NE DELATX.) v PROTIVNOM SLUCHAE, ESLI~$jm$;}\cr K&=\hbox{CHISLO SLUCHAEV, KOGDA V SHAGE R8 $b\le m$, $j=l$;}\cr L&=\hbox{CHISLO SLUCHAEV, KOGDA V SHAGE R8 $b\le m$, $jm$. oDIN PRIEMLEMYJ SPOSOB ISPRAVITX |TOT NEDOSTATOK PREDLOZHEN V OTVETE K UPR.~40. kAK OBMENNAYA PORAZRYADNAYA SORTIROVKA, TAK I BYSTRAYA SORTIROVKA OSNOVANY NA IDEE RAZDELENIYA. zAPISI MENYAYUTSYA MESTAMI DO TEH POR, POKA FAJL NE BUDET RAZBIT NA DVE CHASTI: LEVYJ PODFAJL, V KOTOROM VSE KLYUCHI $\le K$ PRI NEKOTOROM $K$, I PRAVYJ PODFAJL, V KOTOROM VSE KLYUCHI $\ge K$. v BYSTROJ SORTIROVKE V KACHESTVE $K$ VYBIRAETSYA REALXNYJ KLYUCH IZ FAJLA, V TO VREMYA KAK V OBMENNOJ PORAZRYADNOJ SORTIROVKE, PO SUSHCHESTVU, VYBIRAETSYA NEKOTORYJ ISKUSSTVENNYJ KLYUCH NA OSNOVE DVOICHNYH PREDSTAVLENIJ. chTO KASAETSYA ISTORICHESKOJ STORONY DELA, TO OBMENNUYU PORAZRYADNUYU SORTIROVKU OTKRYLI p.~hILXDEBRANDT, g.~iSBITC, X.~rAJZING I zh.~shVARC [{\sl JACM\/}, {\bf 6} (1959), 156--163] PRIMERNO ZA GOD DO IZOBRETENIYA BYSTROJ SORTIROVKI. vOZMOZHNY TAKZHE I DRUGIE SHEMY RAZDELENIYA; NAPRIMER, dZHON mAKKARTI PREDLOZHIL VYBIRATX $K\approx{1\over2}(u+v)$, ESLI IZVESTNO, CHTO VSE KLYUCHI LEZHAT V DIAPAZONE MEZHDU $u$ I~$v$. eSHCHE ODNU STRATEGIYU RAZDELENIYA PREDLOZHIL m.~h.~VAN~eMDEN [{\sl CACM\/}, {\bf 13} (1970), 563--567]: VMESTO TOGO CHTOBY VYBIRATX $K$ ZARANEE, MY "UZNAEM", KAKOVO MOZHET BYTX HOROSHEE ZNACHENIE $K$, SLEDYA V PROCESSE RAZDELENIYA ZA IZMENENIEM VELICHIN $K'=\max(K_l, \ldots, K_i)$ I~$K''=\min(K_j, \ldots, K_r)$. mOZHNO UVELICHIVATX $i$ DO TEH POR, POKA NE VSTRETITSYA KLYUCH, BOLXSHIJ $K'$; ZATEM NACHATX UMENXSHATX $j$, POKA NE VSTRETITSYA KLYUCH, MENXSHIJ $K''$, POSLE CHEGO POMENYATX IH MESTAMI I/ILI UTOCHNITX ZNACHENIYA~$K'$ I~$K''$. eMPIRICHESKIE TESTY DLYA |TOJ INTERVALXNOJ SORTIROVKI POKAZYVAYUT, CHTO ONA TREBUET OKOLO $1.64N\ln N=1.14N\log_2N$ SRAVNENIJ. eTO EDINSTVENNYJ METOD, OBSUZHDAEMYJ V |TOJ KNIGE, DLYA POVEDENIYA KOTOROGO ESHCHE NE NAJDENO ADEKVATNOGO TEORETICHESKOGO OB®YASNENIYA. oBOBSHCHENIE OBMENNOJ PORAZRYADNOJ SORTIROVKI NA SLUCHAJ SISTEMY SCHISLENIYA S OSNOVANIEM, BOLXSHIM 2, OBSUZHDAETSYA V P.~5.2.5. %%158 \section * aSIMPTOTICHESKIE METODY. aNALIZ ALGORITMOV OBMENNOJ SORTIROVKI PRIVODIT K NEKOTORYM OSOBENNO POUCHITELXNYM MATEMATICHESKIM ZADACHAM, KOTORYE POZVOLYAYUT BOLXSHE UZNATX O SPOSOBAH OPREDELENIYA ASIMPTOTICHESKOGO POVEDENIYA FUNKCII. nAPRIMER, PRI ANALIZE METODA PUZYRXKA [FORMULA (9)] MY STOLKNULISX S FUNKCIEJ $$ W_n={1\over n!}\sum_{0\le r m^{1/2+\varepsilon}$ PRENEBREZHIMO MALY.) pUSTX $g_k(x)=x^ke^{-x^2}$ I~$f_k(x)=g_k(x/\sqrt{2m})$. pO FORMULE SUMMIROVANIYA eJLERA PRI~$k\ge 0$ $$ \eqalign{ \sum_{0\le tn^\varepsilon$]}\cr &=\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j