\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
