\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
