\input style %%122 RYJ 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