\input style eTOT ALGORITM VAZHEN NE TOLXKO KAK PROSTOJ METOD SORTIROVKI, NO I POTOMU, CHTO ON CHASTO VSTRECHAETSYA KAK CHASTX DRUGIH ALGORITMOV OBRABOTKI SPISKOV. v TABL.~8 POKAZANY PERVYE NESKOLXKO SHAGOV SORTIROVKI SHESTNADCATI CHISEL, VYBRANNYH NAMI DLYA PRIMEROV. \prog L.(vSTAVKI V SPISOK.) pREDPOLAGAETSYA, CHTO KLYUCH~$K_j$ HRANITSYA V POLE~$|INPUT|+j(0:3)$, a~$L_j$---V POLE~$|INPUT|+j(4:5)$. zNACHENIYA REGISTROV: $|rI1|\equiv j$; $|rI2|\equiv p$; $|rI3|\equiv =q$; $|rA|(0:3)\equiv K$. \code KEY &EQU & 0:3 LINK &EQU & 4:5 START&ENT1 & N & 1 & L1. cIKL PO~$j$, $j\asg N$. &ST1 & INPUT(LINK) & 1 & $L_0\asg N$. &STZ & INPUT+N(LINK)& 1 & $L_N\asg 0$. &JMP & 6F & 1 & pEREHOD K UMENXSHENIYU~$j$. 2H &LD2 & INPUT(LINK) & N-1 & L2. uSTANOVITX~$p$, $q$, $K$. $p\asg L_0$. &ENT3 & 0 & N-1 & $q\asg 0$. &LDA & INPUT,1 & N-1 & $K\asg K_j$. 3H &CMPA & INPUT,2(KEY) & B+N-1-A& L3. sRAVNITX~$K$, $K_p$. &JLE & 5F & B+N-1-A& K~L5, ESLI~$K\le K_p$. 4H &ENT3 & 0,2 & B & L4. pRODVINUTX~$p$, $q$. $q\asg p$. &LD2 & INPUT,3(LINK)& B & $p\asg L_q$. &J2P & 3v & B & k L3, ESLI~$p>0$. 5H &ST1 & INPUT,3(LINK)& N-1 & L5. vSTAVITX V SPISOK. $L_q\asg j$. &ST2 & INPUT,1(LINK)& N-1 & $L_j\asg p$. 6H &DEC1 & 1 & N &J1P & 2v & N & $N>j \ge 1$. \endcode \progend vREMYA RABOTY |TOJ PROGRAMMY RAVNO $7B+14N-3A-6$~EDINIC, GDE~$N$---DLINA FAJLA, $A$---CHISLO PRAVOSTORONNIH MAKSIMUMOV, A~$B$---CHISLO INVERSIJ V ISHODNOJ PERESTANOVKE. (sR. S ANALIZOM PROGRAMMY~S. zAMETXTE, CHTO PROGRAMMA~L NE PEREMESHCHAET ZAPISI V PAMYATI; |TO MOZHNO SDELATX, KAK V UPR.~5.2-12, ZATRATIV DOPOLNITELXNO $20N$~EDINIC VREMENI.) pROGRAMMA~S TREBUET $(9B+10N-3A-9)u$, A TAK KAK $B$~RAVNO PRIMERNO~${1\over 4}N^2$, TO NETRUDNO VIDETX, CHTO ZA SCHET DOPOLNITELXNOGO PROSTRANSTVA PAMYATI, VYDELENNOGO POD POLYA SVYAZI, UDALOSX S|KONOMITX PRIMERNO 22\% VREMENI RABOTY. aKKURATNO PROGRAMMIRUYA, MOZHNO SBERECHX ESHCHE 22\% (SM.~UPR.~33), NO VREMYA RABOTY VSE ZHE OSTANETSYA PROPORCIONALXNYM~$N^2$. \emph{pODVEDEM ITOG SDELANNOMU DO SIH POR.} mY NACHALI S ALGORITMA~S---PROSTOGO I ESTESTVENNOGO ALGORITMA SORTIROVKI, KOTORYJ %%122 VYPOLNYAET OKOLO ${1\over4}N^2$ SRAVNENIJ I OKOLO ${1\over4}N^2$ PEREMESHCHENIJ. mY USOVERSHENSTVOVALI EGO, RASSMOTREV BINARNYE VSTAVKI, PRI KOTORYH VYPOLNYAETSYA OKOLO $N\log_2N$ SRAVNENIJ I ${1\over4}N^2$ PEREMESHCHENIJ. nESKOLXKO IZMENIV STRUKTURU DANNYH, PRIMENIV "DVUHPUTEVYE VSTAVKI", SUMELI SOKRATITX CHISLO PEREMESHCHENIJ DO ${1\over8}N^2$. pRI SORTIROVKE METODOM shELLA "S UBYVAYUSHCHIM SHAGOM" CHISLO SRAVNENIJ I PEREMESHCHENIJ SNIZHAETSYA PRIMERNO DO $N^{1.3}$ DLYA TEH ZNACHENIJ $N$, KOTORYE VSTRECHAYUTSYA NA PRAKTIKE; PRI $N\to\infty$ |TO CHISLO MOZHNO SOKRATITX DO PORYADKA $N(\log_2N)^2$. dALXNEJSHEE STREMLENIE ULUCHSHITX ALGORITM---PUTEM PRIMENENIYA SVYAZANNOJ STRUKTURY DANNYH---PRIVELO NAS K VSTAVKAM V SPISOK, PRI KOTORYH VYPOLNYAETSYA OKOLO ${1\over4}N^2$ SRAVNENIJ, 0 PEREMESHCHENIJ I $2N$ IZMENENIJ SVYAZEJ. mOZHNO LI SOEDINITX LUCHSHIE SVOJSTVA |TIH METODOV, SOKRATIV CHISLO SRAVNENIJ DO PORYADKA $N\log N$, KAK PRI BINARNYH VSTAVKAH, I ISKLYUCHIV PRI |TOM PEREMESHCHENIYA DANNYH, KAK PRI VSTAVKAH \picture{rIS. 13. pRIMER SHEMY uILERA DLYA VSTAVOK V DEREVO.} V SPISOK? oTVET UTVERDITELXNYJ: |TO DOSTIGAETSYA PEREHODOM K DREVOVIDNOJ STRUKTURE. tAKAYA VOZMOZHNOSTX BYLA VPERVYE ISSLEDOVANA OKOLO 1957~G. d.~dZH.~uILEROM, KOTORYJ PREDLOZHIL ISPOLXZOVATX DVUHPUTEVYE VSTAVKI DO TEH POR, POKA NE POYAVITSYA NEOBHODIMOSTX PEREMESHCHATX DANNYE. tOGDA VMESTO TOGO, CHTOBY IH PEREMESHCHATX, VSTAVLYAETSYA UKAZATELX NA NOVUYU OBLASTX PAMYATI, I TOT ZHE SAMYJ METOD REKURRENTNO PRIMENYAETSYA KO VSEM |LEMENTAM, KOTORYE NUZHNO VSTAVITX V |TU NOVUYU OBLASTX PAMYATI. oRIGINALXNYJ METOD uILERA [SM. A. S. Douglas, {\sl Comp. J.,\/} {\bf 2} (1959), 5] PREDSTAVLYAET SOBOJ SLOZHNUYU KOMBINACIYU POSLEDOVATELXNOJ I SVYAZANNOJ PAMYATI S UZLAMI PEREMENNOGO RAZMERA; DLYA NASHIH SHESTNADCATI CHISEL BYLO BY SFORMIROVANO DEREVO, POKAZANNOE NA RIS.~13. aNALOGICHNUYU, NO BOLEE PROSTUYU SHEMU VSTAVKI V DEREVO S ISPOLXZOVANIEM BINARNYH DEREVXEV NEZAVISIMO %% 123 RAZRABOTAL OKOLO 1958~G. k.m.~bERNES-lI [SM. {\sl Comp. J.\/}, {\bf 3} (1960), 174, 184]. sAM |TOT METOD I EGO MODERNIZACII VESXMA VAZHNY KAK DLYA SORTIROVKI, TAK I DLYA POISKA, PO|TOMU PODROBNO ONI OBSUZHDAYUTSYA V GL.~ 6. eSHCHE ODIN PUTX ULUCHSHITX PROSTYE VSTAVKI---POPYTATXSYA VSTAVLYATX NESKOLXKO |LEMENTOV ODNOVREMENNO. eSLI, NAPRIMER, IMEETSYA FAJL IZ 1000 |LEMENTOV I 998 IZ NIH UZHE OTSORTIROVANY, TO ALGORITM S VYPOLNIT ESHCHE DVA PROSMOTRA FAJLA (VSTAVIV SNACHALA $R_{999}$, A POTOM $R_{1000}$). oCHEVIDNO, MOZHNO S|KONOMITX VREMYA, ESLI SNACHALA SRAVNITX KLYUCHI $K_{999}$ c $K_{1000}$ CHTOBY VYYASNITX, KOTORYJ IZ NIH BOLXSHE, A POTOM VSTAVITX IH \emph{OBA} ZA ODIN PROSMOTR FAJLA. kOMBINIROVANNAYA OPERACIYA TAKOGO RODA TREBUET OKOLO $(2/3)N$ SRAVNENIJ I PEREMESHCHENIJ (SR. S UPR.~3.4.2--5) VMESTO DVUH PROSMOTROV, PRIMERNO PO $N/2$ SRAVNENIJ I PEREMESHCHENIJ KAZHDYJ. iNACHE GOVORYA, OBYCHNO BYVAET POLEZNO "GRUPPIROVATX" OPERACII, KOTORYE TREBUYUT DLITELXNOGO POISKA, CHTOBY MOZHNO BYLO VYPOLNITX NESKOLXKO OPERACIJ VMESTE. eSLI DOVESTI |TU IDEYU DO EE ESTESTVENNOGO ZAVERSHENIYA, TO MY ZANOVO OTKROEM DLYA SEBYA SORTIROVKU POSREDSTVOM SLIYANIYA, NASTOLXKO VAZHNUYU, CHTO EJ POSVYASHCHEN OTDELXNYJ PUNKT. \section sORTIROVKA S VYCHISLENIEM ADRESA. tEPERX UZH MY, NESOMNENNO, ISCHERPALI VSE VOZMOZHNYE SPOSOBY USOVERSHENSTVOVATX METOD PROSTYH VSTAVOK, NO DAVAJTE PODUMAEM ESHCHE! pREDSTAVXTE SEBE, CHTO VAM DALI CHISTYJ LIST BUMAGI I SOBIRAYUTSYA DIKTOVATX KAKIE-TO SLOVA. vASHA ZADACHA---ZAPISATX IH V ALFAVITNOM PORYADKE I VERNUTX LISTOK S OTSORTIROVANNYM SPISKOM SLOV. uSLYSHAV SLOVO NA BUKVU a, VY BUDETE STREMITXSYA ZAPISATX EGO BLIZHE K VERHNEMU KRAYU STRANICY, TOGDA KAK SLOVO NA BUKVU ya BUDET, PO-VIDIMOMU, POMESHCHENO BLIZHE K NIZHNEMU KRAYU STRANICY I~T.~D. aNALOGICHNYJ SPOSOB PRIMENYAETSYA PRI RASSTANOVKE KNIG NA POLKE PO FAMILIYAM AVTOROV, ESLI KNIGI BERUTSYA S POLA V SLUCHAJNOM PORYADKE: STAVYA KNIGU NA POLKU, VY OCENIVAETE EE KONECHNOE POLOZHENIE, SOKRASHCHAYA TAKIM OBRAZOM CHISLO NEOBHODIMYH SRAVNENIJ I PEREMESHCHENIJ. (eFFEKTIVNOSTX PROCESSA POVYSHAETSYA, ESLI NA POLKE IMEETSYA NEMNOGO BOLXSHE MESTA, CHEM |TO ABSOLYUTNO NEOBHODIMO.) tAKOJ METOD MASHINNOJ SORTIROVKI VPERVYE PREDLOZHILI iSAAK I sINGLTON, [{\sl JACM\/}, {\bf 3} (1956), 169--174]; ON POLUCHIL DALXNEJSHEE RAZVITIE V RABOTE kRONM|LA I tARTARA [Proc. ACM Nat'l Conf., {\bf 21} (1966), 331--337]. sORTIROVKA S VYCHISLENIEM ADRESA OBYCHNO TREBUET DOPOLNITELXNOGO PROSTRANSTVA PAMYATI LIBO DLYA TOGO, CHTOBY OSTAVITX DOSTATOCHNO SVOBODNOGO MESTA I NE DELATX MNOGO LISHNIH PEREMESHCHENIJ, LIBO DLYA HRANENIYA VSPOMOGATELXNYH TABLIC, KOTORYE BY POZVOLYALI UCHITYVATX NERAVNOMERNOSTX RASPREDELENIYA KLYUCHEJ. (sM.\ SORTIROVKU RASPREDELYAYUSHCHIM PODSCHETOM (ALGORITM~5.2D), %% 124 \bye