\input style
\chapnotrue
\chapno=5
\subchno=2
\subsubchno=0
\alg D.(rASPREDELYAYUSHCHIJ PODSCHET.) eTOT ALGORITM V PREDPOLOZHENII, CHTO VSE 
KLYUCHI---CELYE CHISLA V DIAPAZONE $u\le K_j\le v$ PRI $1\le j\le N$, SORTIRUET 
ZAPISI $R_1$, \dots, $R_N$, ISPOLXZUYA VSPOMOGATELXNUYU TABLICU 
$|COUNT|[u]$, \dots, $|COUNT|[v]$. v KONCE RABOTY ALGORITMA VSE ZAPISI V 
TREBUEMOM PORYADKE PERENOSYATSYA V OBLASTX VYVODA $S_1$, \dots, $S_N$.

\st[sBROSITX SCHETCHIKI.] uSTANOVITX $|COUNT|[u]$, \dots, 
$|COUNT|[v]$ RAVNYMI NULYU.

\st[cIKL PO $j$.] vYPOLNITX SHAG \stp{3} PRI $1\le j\le N$,  ZATEM PEREJTI 
K SHAGU \stp{4}.

\st[uVELICHITX $|COUNT| [K_j]$.] uVELICHITX ZNACHENIE $|COUNT|[K_j]$ NA 1.    

\st[sUMMIROVANIE.] (k |TOMU MOMENTU ZNACHENIE $|COUNT|[i]$ ESTX CHISLO 
KLYUCHEJ, RAVNYH $i$.)  uSTANOVITX 
$|COUNT|[i]\asg COUNT[i]+COUNT[i-l]$ PRI $i=u+l$, $u+2$, \dots, $v$.

\st[cIKL PO $j$.] (k |TOMU MOMENTU ZNACHENIE $|COUNT|[i]$ ESTX CHISLO KLYUCHEJ,
 MENXSHIH ILI RAVNYH $i$, V CHASTNOSTI $|COUNT|[v]=N$.) vYPOLNITX SHAG 
\stp{6} PRI $j=N$, $N-1$, \dots, 1 I ZAVERSHITX RABOTU ALGORITMA.

\stp[vYVOD $R_j$.] uSTANOVITX $i\asg |COUNT|[K_j]$, $S_i\asg R_i$, I 
$|COUNT| [K_j]\asg i-1$.
\algend
\noindent pRIMER PRIMENENIYA |TOGO ALGORITMA PRIVEDEN V UPR.~6; PROGRAMMU 
DLYA MASHINY \MIX\ MOZHNO NAJTI V UPR.~9. pRI SFORMULIROVANNYH VYSHE 
USLOVIYAH |TO OCHENX BYSTRAYA PROCEDURA .SORTIROVKI.

sORTIROVKA POSREDSTVOM SRAVNENIYA I PODSCHETA, KAK, V ALGORITME C, VPERVYE 
UPOMINAETSYA V RABOTE e.~X.~fR|NDA 
[{\sl JACM\/},{\bf 3} (1965), 152],. HOTYA ON I NE ZAYAVIL O NEJ KAK O SVOEM 
SOBSTVENNOM IZOBRETENII. rASPREDELYAYUSHCHIJ PODSCHET, KAK V ALGORITME D, 
VPERVYE RAZRABOTAN X.~sXYUVORDOM V 1954~G. I ISPOLXZOVALSYA PRI PORAZRYADNOJ 
SORTIROVKE, KOTORUYU MY OBSUDIM POZZHE (SM. P.~5.2.5); |TOT METOD TAKZHE -BYL 
OPUBLIKOVAN POD NAZVANIEM "Mathsort" V RABOTE W. Feurzig, {\sl CACM\/}, 
{\bf 3} (I960), 601.

\excercises
\ex[15] bUDET LI RABOTATX ALGORITM s, ESLI V SHAGE s2 ZNACHENIE s 
BUDET IZMENYATXSYA OT $2$ DO $N$, A NE OT $N$ DO~$2$? chTO PROIZOJDET, ESLI V 
SHAGE Cz ZNACHENIE $j$ BUDET IZMENYATXSYA OT $1$ DO $i-1$?

\ex[21] pOKAZHITE, CHTO ALGORITM C RABOTAET PRAVILXNO I PRI 
NALICHII ODINAKOVYH KLYUCHEJ. eSLI $K_j=K_i$  I $j<i$, TO GDE OKAZHETSYA V 
KONCE KONCOV $R_j$---DO ILI POSLE $R_i$?

\rex[21] bUDET LI ALGORITM C RABOTATX PRAVILXNO, ESLI V SHAGE C4 ZAMENITX 
PROVERKU "$K_i<K_j$"  NA "$K_i\le K_j$"?

\ex[16] nAPISHITE \MIX-PROGRAMMU, KOTORAYA ZAVERSHIT SORTIROVKU, NACHATUYU 
PROGRAMMOJ C; VASHA PROGRAMMA DOLZHNA POMESTITX KLYUCHI V YACHEJKI $|OUTPUT|+1$, 
\dots, $|OUTPUT|+N$ V VOZRASTAYUSHCHEM PORYADKE. sKOLXKO VREMENI ZATRATIT NA 
|TO VASHA PROGRAMMA?
%% 101

\ex[22] uLUCHSHITSYA LI PROGRAMMA C V REZULXTATE SLEDUYUSHCHIH IZMENENIJ?
$$
\indent\vtop{
\halign{#\bskip\hfill&\bskip |#|\hfill&|#|\hfill\cr
vVESTI NOVUYU STROKU 8A:  & INCX  & 0, 2 \cr
iZMENITX STROKU 10:      & JGE    &5F\cr
iZMENITX STROKU 14:      & DECX &1\cr
iSKLYUCHITX STROKU 15. \cr
}
}
$$


\ex[18] pROMODELIRUJTE VRUCHNUYU RABOTU ALGORITMA D,  POKAZYVAYA 
PROMEZHUTOCHNYE REZULXTATY, POLUCHAYUSHCHIESYA PRI SORTIROVKE 16 ZAPISEJ
$$
\hbox{5t, 0s, 5U, 00, 9, 1N, 8S, 2R, 6A, 4A, 1G, 5L, 6T, 61, 70, 7N.}
$$
zDESX CIFRY---|TO KLYUCHI, A BUKVY---SOPUTSTVUYUSHCHAYA INFORMACIYA V ZAPISYAH.

\ex[13] yaVLYAETSYA LI ALGORITM D ALGORITMOM "USTOJCHIVOJ" SORTIROVKI? 
\ex[15] bUDET LI ALGORITM D RABOTATX PRAVILXNO, ESLI V SHAGE D5 ZNACHENIE 
$j$ BUDET IZMENYATXSYA OT $1$ DO $N$, A NE OT $N$ DO $1$?

\ex[23] nAPISHITE \MIX-PROGRAMMU DLYA ALGORITMA D, ANALOGICHNUYU PROGRAMME C 
I UPR.~4. vYRAZITE VREMYA RABOTY VASHEJ PROGRAMMY V VIDE FUNKCII OT $N$ I $(v-u)$.

\ex[25] pREDLOZHITE |FFEKTIVNYJ ALGORITM, KOTORYJ BY ZAMENYAL $N$ VELICHIN 
$(R_1, \dots, R_N)$ SOOTVETSTVENNO NA $(R_{p(1)}, \dots, R_{p(1)}))$, ESLI 
DANY ZNACHENIYA $R_1$, \dots, $R_N$ I PERESTANOVKA $p(1)$ \dots $p (N)$ 
MNOZHESTVA 
$\{1, \dots,  N\}$. pOSTARAJTESX NE ISPOLXZOVATX IZLISHNEGO PROSTRANSTVA 
PAMYATI. (eTA ZADACHA VOZNIKAET, KOGDA TREBUETSYA PERERAZMESTITX V PAMYATI 
ZAPISI POSLE SORTIROVKI TABLICY ADRESOV, NE RASHODUYA PAMYATX NA $2N$ ZAPISEJ.)

\ex[M27] nAPISHITE \MIX-PROGRAMMU DLYA ALGORITMA IZ UPR.~10 I 
PROANALIZIRUJTE EE. |FFEKTIVNOSTX.

\rex[25] pREDLOZHITE |FFEKTIVNYJ ALGORITM PERERAZMESHCHENIYA V PAMYATI ZAPISEJ 
$R_1$, \dots, $R_N$ V OTSORTIROVANNOM PORYADKE POSLE ZAVERSHENIYA SORTIROVKI 
SPISKA (RIS.~7). pOSTARAJTESX NE ISPOLXZOVATX IZLISHNEGO PROSTRANSTVA PAMYATI.

\rex[27] aLGORITMU D TREBUETSYA  PROSTRANSTVO DLYA $2N$ ZAPISEJ 
$R_1$, \dots $R_N$  I $S_1$, \dots, $S_N$. pOKAZHITE, CHTO MOZHNO OBOJTISX 
PROSTRANSTVOM DLYA $N$ ZAPISEJ $R_1$, \dots, $R_N$, ESLI VMESTO SHAGOV D5 I 
D6 PODSTAVITX NOVUYU UPORYADOCHIVAYUSHCHUYU PROCEDURU. (tAKIM OBRAZOM, ZADACHA 
SOSTOIT V TOM, CHTOBY RAZRABOTATX ALGORITM, KOTORYJ BY PERERAZMESHCHAL ZAPISI 
$R_1$, \dots, $R_N$.  OSNOVYVAYASX NA ZNACHENIYAH
$$
|COUNT| [u], \ldots |COUNT| [v]
$$
POSLE VYPOLNENIYA SHAGA D4, NE ISPOLXZUYA DOPOLNITELXNOJ PAMYATI; |TO, 
PO SUSHCHESTVU, OBOBSHCHENIE ZADACHI, RASSMOTRENNOJ V UPR. 10.)

\subsubchap{sORTIROVKA VSTAVKAMI} % 5.2.1
oDNO IZ VAZHNYH SEMEJSTV-METODOV SORTIROVKI OSNOVANO NA UPOMYANUTOM V 
NACHALE \S~5.2 SPOSOBE, KOTORYM POLXZUYUTSYA IGROKI V BRIDZH; PREDPOLAGAETSYA, 
CHTO PERED RASSMOTRENIEM ZAPISI $R_j$ PREDYDUSHCHIE ZAPISI $R_1$, \dots, 
$R_{j-1}$ UZHE UPORYADOCHENY, I $R_j$ VSTAVLYAETSYA V SOOTVETSTVUYUSHCHEE MESTO. nA 
OSNOVE |TOJ SHEMY VOZMOZHNY NESKOLXKO LYUBOPYTNYH VARIACIJ.

\section pROSTYE VSTAVKI. pROSTEJSHAYA SORTIROVKA VSTAVKAMI OTNOSITSYA K 
NAIBOLEE OCHEVIDNYM. pUSTX $1 <j  \le  N$  I  ZAPISI $R_1$, \dots, $R_{j-1}$
%% 102
UZHE RAZMESHCHENY TAK, CHTO
$$
K_1\le K_2\le \ldots \le K_{j-1}.
$$
(nAPOMNIM, CHTO V |TOJ GLAVE CHEREZ $K_j$ OBOZNACHAETSYA KLYUCH ZAPISI $R_j$.) 
bUDEM SRAVNIVATX PO OCHEREDI $K_j$ S $K_{j-1}$, $K_{j-2}$, \dots DO TEH POR, 
POKA NE OBNARUZHIM, CHTO ZAPISX $R_j$ SLEDUET VSTAVITX MEZHDU $R_i$ I 
$R_{i+1}$; TOGDA PODVINEM ZAPISI $R_{i+1}$, \dots, $R_{j-1}$ NA ODNO MESTO 
VVERH I POMESTIM NOVUYU ZAPISX V POZICIYU $i+1$. uDOBNO SOVMESHCHATX OPERACII 
SRAVNENIYA I PEREMESHCHENIYA, PEREMEZHAYA IH DRUG S DRUGOM, KAK POKAZANO V 
SLEDUYUSHCHEM ALGORITME; POSKOLXKU ZAPISX $R_j$ KAK BY "PRONIKAET NA 
POLOZHENNYJ EJ UROVENX", |TOT SPOSOB CHASTO NAZYVAYUT \dfn{PROSEIVANIEM}, 
ILI \dfn{POGRUZHENIEM}.

\alg S.(sORTIROVKA PROSTYMI VSTAVKAMI.) 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$.

\st[cIKL. PO $j$.] vYPOLNITX SHAGI OT \stp{2} DO \stp{5} PRI  $j= 2$, 3, 
\dots, $N$ I POSLE |TOGO ZAVERSHITX ALGORITM.
\picture{rIS. 10.  aLGORITM S: PROSTYE VSTAVKI.}
\st[uSTANOVITX $i$, $K$, $R$.] uSTANOVITX $i\asg j-1$,  $K\asg K_j$,  
$R\asg R_j$.(v POSLEDUYUSHCHIH SHAGAH MY POPYTAEMSYA VSTAVITX ZAPISX $R$ V 
NUZHNOE MESTO, SRAVNIVAYA $K$ S $K_i$ PRI UBYVAYUSHCHIH ZNACHENIYAH $i$.)

\st[sRAVNITX $K$ S  $K_i$.] eSLI $K\ge K_i$, TO PEREJTI K SHAGU  
\stp{5}. (mY NASHLI ISKOMOE MESTO DLYA ZAPISI $R$.)

\st[pEREMESTITX $R_i$, UMENXSHITX $i$.] uSTANOVITX $R_{i+1}\asg R_i$,
 $i\asg i-1$. eSLI $i>0$, TO VERNUTXSYA K SHAGU \stp{3}. (eSLI $i=0$, TO 
$K$---NAIMENXSHIJ IZ RASSMOTRENNYH DO SIH POR KLYUCHEJ, A, ZNACHIT, ZAPISX $R$ 
DOLZHNA ZANYATX PERVUYU POZICIYU.)
\st[$R$ NA MESTO $R_{i+1}$.] uSTANOVITX $R_{i+1}\asg R$.
\algend
v TABL.~1 POKAZANO PRIMENENIE ALGORITMA S K SHESTNADCATI CHISLAM, VZYATYM 
NAMI DLYA PRIMEROV. eTOT METOD CHREZVYCHAJNO PROSTO REALIZUETSYA NA 
VYCHISLITELXNOJ MASHINE; FAKTICHESKI SLEDUYUSHCHAYA \MIX-PROGRAMMA---SAMAYA 
KOROTKAYA IZ VSEH PRIEMLEMYH PROGRAMM SORTIROVKI V |TOJ KNIGE.
%% 103

\prog S.(sORTIROVKA PROSTYMI VSTAVKAMI). zAPISI, KOTORYE NADO 
OTSORTIROVATX, NAHODYATSYA V YACHEJKAH $|INPUT|+1$, \dots,  $|INPUT|+N$; ONI 
SORTIRUYUTSYA V TOJ ZHE OBLASTI PO KLYUCHU, ZANIMAYUSHCHEMU ODNO SLOVO CELIKOM. 
zDESX $|rI1|\equiv j-N$; $|rI2|\equiv i$, $|rA|\equiv R\equiv K$; 
PREDPOLAGAETSYA, CHTO $N\ge 2$.
\code
START &ENT1 &2-N       &1      & S1.cIKL no $j$. $j\asg 2$. 
2H    &LDA  &INPUT+N,1 &N-1    & S2. uSTANOVITX $i$, $K$, $R$
      &ENT2 &N-1,1     &N-1    & $i\asg j-1$.
3H    &CMPA &INPUT,2   &B+N-1-A& S3. sRAVNITX $K$, $K_i$
      &JGE  &5F        &B+N-1-A& k S5, ESLI $K\ge K_i$.
4H    &LDX  &INPUT,2   &v      & S4. pEREMESTITX $R_i$, UMENXSHITX $i$
      &STX  &INPUT+1,2 &v      & $R_{i+1}\asg R_i$.
      &DEC2 &1         &B      & $i\asg i-1$.
      &J2P  &3B        &B      & k S3, ESLI $i>0$.
5H    &STA  &INPUT+1,2 &N-1    & S5. $R$ NA MESTO $R_i+1$.
      &INC1 &1         &N-1
      &J1NP &2B        &N-1    & $2\le j \le N$.
\endcode
\progend
vREMYA RABOTY |TOJ PROGRAMMY RAVNO $9B+10N-3A-9$ EDINIC, GDE $N$---CHISLO 
SORTIRUEMYH ZAPISEJ, $A$---CHISLO SLUCHAEV, KOGDA V SHAGE S4 ZNACHENIE $i$ 
UBYVAET DO 0, A $B$---CHISLO PEREMESHCHENIJ. yaSNO, CHTO $A$ RAVNO CHISLU SLUCHAEV, 
KOGDA $K_j<(K_1, \ldots, K_{j-1})$ PRI $1< j \le N$, T. E. |TO CHISLO 
LEVOSTORONNIH MINIMUMOV---VELICHINA, KOTORAYA BYLA TSHCHATELXNO ISSLEDOVANA V 
P.~1.2.10. nEMNOGO PODUMAV, NETRUDNO PONYATX, CHTO $B$---TOZHE IZVESTNAYA 
VELICHINA: CHISLO PEREMESHCHENIJ PRI FIKSIROVANNOM $j$ RAVNO CHISLU INVERSIJ 
KLYUCHA $K_j$, TAK CHTO $B$ RAVNO CHISLU INVERSIJ PERESTANOVKI $K_1$, $K_2$, 
\dots, $K_N$. sLEDOVATELXNO, SOGLASNO FORMULAM (1.2.10--16) I (5.1.1--12, 
13),
$$
\eqalign{
A&=(\min 0, \ave H_N-1, \max N-1,  \dev\sqrt{H_n-H_n^{(2)}});\cr
B&=(\min 0, \ave (N^2-N)/4, \max (N^2-N)/2,
\dev\sqrt{N(N-1)(N+2.5)/6}),\cr
}
$$
A SREDNEE VREMYA RABOTY PROGRAMMY S V PREDPOLOZHENII, CHTO KLYUCHI RAZLICHNY I 
RASPOLOZHENY V SLUCHAJNOM PORYADKE, RAVNO $(2.25N^2+7.75N-3H_N-6)u$. v 
UPR.~33 POKAZANO, KAK MOZHNO CHUTX-CHUTX UMENXSHITX |TO VREMYA.

pRIVEDENNYE V KACHESTVE PRIMERA V TABL.~1 DANNYE SODERZHAT 16~|LEMENTOV; 
IMEYUTSYA DVA LEVOSTORONNIH MINIMUMA, 087 I~061, I, KAK MY VIDELI V 
PREDYDUSHCHEM PUNKTE, 41 INVERSIYA. sLEDOVATELXNO, $N=16$, $A=2$, $B=41$, A 
OBSHCHEE VREMYA SORTIROVKI RAVNO $514u$.

\section bINARNYE VSTAVKI I DVUHPUTEVYE VSTAVKI. kOGDA PRI 
SORTIROVKE PROSTYMI VSTAVKAMI OBRABATYVAETSYA $j$-YA ZAPISX, EE KLYUCH 
SRAVNIVAETSYA V SREDNEM PRIMERNO S $j/2$ RANEE OTSORTIROVANNYMI KLYUCHAMI; 
%% 104
{\catcode`\!=\active\def!{\hidewidth{}_{\hbox{\tentt\char"5E}}}
 \catcode`\@=\active\def@{{}_{\hbox{\tentt\char"5E}}\hidewidth}
 \catcode`\:=\active\def:{\hidewidth{\char`\:}}
\ctable{\bskip$#$\bskip&&\bskip$#$\bskip\cr
\noalign{\rightline{tABLICA 1}}
\noalign{\centerline{pRIMER PRIMENENIYA PROSTYH VSTAVOK}}
!503&:087 &\cr
 087& 503@&:512\cr
!087& 503 & 512 &:061\cr
 061& 087 & 503 & 512@&:908\cr
 061& 087@& 503 & 512 & 908 &:170\cr
 061& 087 & 170 & 503 & 512@& 908 &:897\cr
\noalign{\line{\null\leaders\hbox to 1em{\hss.\hss}\hfill\null}}\cr
 061& 087 & 154 & 170 & 275 &426 &503 &509 &512 &612 &653 &677@&765 &897 &908 &:703\cr
 061& 087 & 154 & 170 & 275 &426 &503 &509 &512 &612 &653 &677 &703 &765 &897 & 908\cr
}
}
PO|TOMU OBSHCHEE CHISLO SRAVNENIJ RAVNO 
PRIBLIZITELXNO $(1+2+\cdots+N)/2\approx N^2/4$, A |TO OCHENX MNOGO, DAZHE 
ESLI $N$ UMERENNO VELIKO. v P.~6.2.1 MY IZUCHIM METODY "BINARNOGO POISKA",
 KOTORYE UKAZYVAYUT, KUDA VSTAVLYATX $j$-J |LEMENT POSLE PRIBLIZITELXNO 
$\log_2 j$ SOOTVETSTVUYUSHCHIM OBRAZOM VYBRANNYH SRAVNENIJ. nAPRIMER, ESLI 
VSTAVLYAETSYA 64-YA ZAPISX, MOZHNO SNACHALA SRAVNITX KLYUCH $K_{64}$ S 
$K_{32}$; ZATEM, ESLI ON MENXSHE, SRAVNIVAEM EGO S $K_{16}$, ESLI BOLXSHE---S 
$K_{48}$ I T. D., TAK CHTO MESTO DLYA $R_{64}$ BUDET NAJDENO POSLE VSEGO 
LISHX SHESTI SRAVNENIJ. oBSHCHEE CHISLO SRAVNENIJ DLYA $N$ VSTAVLYAEMYH |LEMENTOV 
RAVNO PRIBLIZITELXNO $N \log_2 N$, CHTO SUSHCHESTVENNO LUCHSHE, CHEM $N^2/4$; V 
P.~6.2.1 POKAZANO, CHTO SOOTVETSTVUYUSHCHAYA PROGRAMMA NE OBYAZATELXNO NAMNOGO 
SLOZHNEE, CHEM PROGRAMMA DLYA PROSTYH VSTAVOK. eTOT METOD NAZYVAETSYA 
\dfn{BINARNYMI VSTAVKAMI}. oN UPOMINALSYA dZHONOM mOCHLI ESHCHE V 1946~G., V 
PERVOJ PUBLIKACII PO MASHINNOJ SORTIROVKE.

nEPRIYATNOSTX SOSTOIT V TOM, CHTO BINARNYE VSTAVKI RESHAYUT ZADACHU TOLXKO 
NAPOLOVINU: 
POSLE TOGO, KAK MY NASHLI, KUDA  VSTAVLYATX ZAPISX $R_j$, VSE 
RAVNO NUZHNO PODVINUTX PRIMERNO $j/2$ RANEE OTSORTIROVANNYH ZAPISEJ, CHTOBY 
OSVOBODITX MESTO DLYA $R_j$ TAK CHTO OBSHCHEE VREMYA RABOTY OSTAETSYA, PO 
SUSHCHESTVU, PROPORCIONALXNYM $N_2$. nEKOTORYE VYCHISLITELXNYE MASHINY 
(NAPRIMER, IBM 705) IMEYUT VSTROENNYE INSTRUKCII "PEREBROSKI", 
VYPOLNYAYUSHCHIE OPERACII PEREMESHCHENIYA S BOLXSHOJ SKOROSTXYU, NO S ROSTOM $N$ 
ZAVISIMOSTX OT $N^2$ V KONCE KONCOV NACHINAET PREOBLADATX, nAPRIMER, ANALIZ,
 PROVEDENNYJ X. n|GDEROM 
[{\sl CACM\/}, {\bf 3} (1960), 618--620],
POKAZYVAET, CHTO NE SLEDUET REKOMENDOVATX BINARNYE VSTAVKI PRI SORTIROVKE 
BOLEE $N=128$ ZAPISEJ NA MASHINE IBM~705, ESLI KAZHDAYA ZAPISX SOSTOIT IZ 80 
LITER; ANALOGICHNYJ ANALIZ PRIMENIM I K DRUGIM MASHINAM.
%% 105
{
\catcode`\!=\active\def!{\hidewidth{}_{\hbox{\tentt\char"5E}}}
 \catcode`\@=\active\def@{{}_{\hbox{\tentt\char"5E}}\hidewidth}
 \catcode`\:=\active\def:{\hidewidth{\char`\:}}
\ctable{\bskip$#$\bskip&&\bskip$#$\bskip\cr
\noalign{\rightline{tABLICA 2}}
\noalign{\centerline{dVUHPUTEVYE VSTAVKI}}
   &   &   &     &!503 \cr
   &   &   & 087 & 503@ \cr
   &   &   &!087 & 503 &512 \cr
   &   &061& 087 & 503 &512@ \cr
   &   &061& 087@& 503 &512 & 908 \cr
   &061&087& 170 & 503 &512 &@908 \cr
   &061&087& 170@& 503 &512 & 897 & 908 \cr
061&087&170& 276 & 503 &512 & 897 & 908 \cr
}
}

rAZUMEETSYA, IZOBRETATELXNYJ PROGRAMMIST MOZHET PRIDUMATX KAKIE-NIBUDX 
SPOSOBY, POZVOLYAYUSHCHIE SOKRATITX CHISLO NEOBHODIMYH PEREMESHCHENIJ; PERVYJ 
TAKOJ PRIEM, PREDLOZHENNYJ V NACHALE 50-H GODOV, PROILLYUSTRIROVAN V 
TABL.~2. zDESX PERVYJ - |LEMENT POMESHCHAETSYA V SEREDINU OBLASTI VYVODA, I 
MESTO DLYA POSLEDUYUSHCHIH |LEMENTOV OSVOBOZHDAETSYA PRI POMOSHCHI SDVIGOV VLEVO ILI 
VPRAVO, TUDA, KUDA UDOBNEE. tAKIM OBRAZOM UDAETSYA S|KONOMITX PRIMERNO 
POLOVINU VREMENI RABOTY PO SRAVNENIYU S PROSTYMI VSTAVKAMI ZA SCHET 
NEKOTOROGO USLOZHNENIYA PROGRAMMY. mOZHNO PRIMENYATX |TOT METOD, ISPOLXZUYA NE 
BOLXSHE PAMYATI, CHEM TREBUETSYA DLYA $N$ ZAPISEJ (SM. UPR. 6), NO MY NE STANEM 
DOLXSHE ZADERZHIVATXSYA NA TAKIH "DVUHPUTEVYH" VSTAVKAH, TAK KAK 
BYLI RAZRABOTANY GORAZDO BOLEE INTERESNYE METODY.

\section mETOD shELLA. dLYA ALGORITMA SORTIROVKI, KOTORYJ KAZHDYJ 
RAZ PEREMESHCHAET ZAPISX TOLXKO NA ODNU POZICIYU, SREDNEE VREMYA RABOTY BUDET V 
LUCHSHEM SLUCHAE PROPORCIONALXNO $N^2$, POTOMU CHTO V PROCESSE SORTIROVKI 
KAZHDAYA ZAPISX DOLZHNA PROJTI V SREDNEM CHEREZ $N/3$ POZICIJ (SM. UPR.~7). 
pO|TOMU, ESLI MY HOTIM POLUCHITX METOD, SUSHCHESTVENNO PREVOSHODYASHCHIJ PO 
SKOROSTI PROSTYE VSTAVKI, TO NEOBHODIM NEKOTORYJ MEHANIZM, S POMOSHCHXYU 
KOTOROGO ZAPISI MOGLI BY PEREMESHCHATXSYA BOLXSHIMI SKACHKAMI, A NE KOROTKIMI SHAZHKAMI.

tAKOJ METOD PREDLOZHEN V 1959~G. dONALXDOM l. shELLOM [{\sl CACM\/}, {\bf 2} 
(July, 1959), 30--32]; MY BUDEM NAZYVATX EGO \dfn{SORTIROVKOJ S UBYVAYUSHCHIM 
SHAGOM}. v TABL.~3 PROILLYUSTRIROVANA OBSHCHAYA IDEYA, LEZHASHCHAYA V OSNOVE |TOGO 
METODA. sNACHALA DELIM 16 ZAPISEJ NA 8 GRUPP PO DVE ZAPISI V KAZHDOJ 
GRUPPE: $(R_1, R_9)$, $(R_2, R_{10})$, \dots, $(R_8, R_{16})$. v 
REZULXTATE SORTIROVKI KAZHDOJ GRUPPY ZAPISEJ PO OTDELXNOSTI PRIHODIM KO 
VTOROJ STROKE TABL. 3,
%% 106
\picture{tABLICA 3}
|TO NAZYVAETSYA "PERVYM PROSMOTROM". zAMETIM, CHTO |LEMENTY 154 I 512 
POMENYALISX MESTAMI, A 908 I 897 PEREMESTILISX VPRAVO. rAZDELIM TEPERX 
ZAPISI NA CHETYRE GRUPPY PO CHETYRE V KAZHDOJ:
$(R_1, R_5, R_9, R_{13})$, \dots, $(R_4, R_8, R_{12}, R_{16})$---I OPYATX 
OTSORTIRUEM KAZHDUYU GRUPPU V OTDELXNOSTI; |TOT VTOROJ PROSMOTR PRIVODIT K 
TRETXEJ STROKE TABLICY. pRI TRETXEM PROSMOTRE SORTIRUYUTSYA DVE GRUPPY PO 
VOSEMX ZAPISEJ; PROCESS ZAVERSHAETSYA CHETVERTYM PROSMOTROM, VO VREMYA 
KOTOROGO SORTIRUYUTSYA VSE 16 ZAPISEJ. v KAZHDOM IZ |TIH PROMEZHUTOCHNYH 
PROCESSOV SORTIROVKI UCHASTVUYUT LIBO SRAVNITELXNO KOROTKIE FAJLY, LIBO 
UZHE SRAVNITELXNO HOROSHO UPORYADOCHENNYE FAJLY, PO|TOMU NA KAZHDOM 
|TAPE MOZHNO POLXZOVATXSYA PROSTYMI VSTAVKAMI; ZAPISI DOVOLXNO 
BYSTRO DOSTIGAYUT SVOEGO KONECHNOGO POLOZHENIYA.

pOSLEDOVATELXNOSTX SHAGOV 8, 4, 2, 1 NE SLEDUET SCHITATX NEZYBLEMOJ, MOZHNO 
POLXZOVATXSYA \emph{LYUBOJ} POSLEDOVATELXNOSTXYU $h_t$, $h_{t-1}$, \dots, 
$h_1$, V KOTOROJ POSLEDNIJ SHAG $h_1$ RAVEN 1. nAPRIMER, V TABL.~4 BUDET 
POKAZANA SORTIROVKA TEH ZHE DANNYH S SHAGAMI 7, 5, 3, 1. oDNI 
POSLEDOVATELXNOSTI OKAZYVAYUTSYA GORAZDO LUCHSHE DRUGIH; MY OBSUDIM VYBOR 
POSLEDOVATELXNOSTEJ SHAGOV POZZHE.

\alg D.(sORTIROVKA S UBYVAYUSHCHIM SHAGOM.) 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$. dLYA 
UPRAVLENIYA PROCESSOM SORTIROVKI ISPOLXZUETSYA VSPOMOGATELXNAYA 
POSLEDOVATELXNOSTX SHAGOV $h_t$, $h_{t-1}$, \dots, $h_1$, GDE $h_1=l$; 
PRAVILXNO VYBRAV |TI PRIRASHCHENIYA, MOZHNO ZNACHITELXNO SOKRATITX VREMYA 
SORTIROVKI. pRI $t = 1$ |TOT ALGORITM SVODITSYA K ALGORITMU S.

\st[cIKL PO $s$.] vYPOLNITX SHAG \stp{2} PRI $s=t$,  $t-1$, \dots, 1,
POSLE CHEGO ZAVERSHITX RABOTU ALGORITMA.

\st[cIKL PO $j$.] uSTANOVITX $h\asg h_s$ I VYPOLNITX SHAGI \stp{3}, \dots
%% 107
\stp{6} PRI $h<j\le N$. (dLYA SORTIROVKI |LEMENTOV, OTSTOYASHCHIH DRUG OT 
DRUGA NA $h$ POZICIJ, VOSPOLXZUEMSYA PROSTYMI VSTAVKAMI I V REZULXTATE 
POLUCHIM $K_i\le K_{i+h}$ PRI $1\le i\le N-h$. shAGI \stp{3}, \dots, \stp{6},
 PO SUSHCHESTVU, TAKIE ZHE, KAK SOOTVETSTVENNO S2, \dots, S5 V ALGORITME S.) 

\st[uSTANOVITX $i$, $K$, $R$.] uSTANOVITX $i\asg j-h$, $K\asg K_j$,
$R\asg R_j$.

\st[sRAVNITX $K$, $K_i$.] eSLI $K\ge K_i$, TO PEREJTI K SHAGU \stp{6}.

\st[pEREMESTITX $R_i$, UMENXSHITX $i$.] uSTANOVITX $R_{i+h}\asg R_i$,
ZATEM $i\asg i-h$. eSLI $i >0$, TO VOZVRATITXSYA K SHAGU \stp{4}.

\st[$R$ NA MESTO $R_{i+h}$.] uSTANOVITX $R_{i+h}\asg R$.
\algend

sOOTVETSTVUYUSHCHAYA \MIX-PROGRAMMA NE NAMNOGO DLINNEE, CHEM NASHA PROGRAMMA DLYA 
PROSTYH VSTAVOK. sTROKI 08--19 |TOJ PROGRAMMY PERENESENY IZ PROGRAMMY S 
V BOLEE OBSHCHIJ KONTEKST ALGORITMA D.

\prog D.(sORTIROVKA S UBYVAYUSHCHIM SHAGOM.) pREDPOLAGAETSYA, CHTO SHAGI 
SORTIROVKI HRANYATSYA VO VSPOMOGATELXNOJ TABLICE I $h_s$ NAHODITSYA V YACHEJKE 
$|H|+s$; VSE SHAGI SORTIROVKI MENXSHE $N$. sODERZHIMOE REGISTROV: 
$|rI1|\equiv j-N$; $|rI2|\equiv i$; $|rA|\equiv R \equiv K$; 
$|rI3|\equiv s$; $|rI4|\equiv h$. zAMETIM, CHTO |TA PROGRAMMA SAMA SEBYA 
IZMENYAET. eTO 
SDELANO DLYA TOGO, CHTOBY DOBITXSYA BOLEE |FFEKTIVNOGO VYPOLNENIYA 
VNUTRENNEGO CIKLA.
\code
START &ENT3 &t        &1        & D1. cIKL PO $s$. $s\asg t$.
1H    &LD4  &H,3      &T        & D2. cIKL PO $j$.$h\asg h_s$.
      &ENT1 &INPUT,4  &t        & iZMENITX ADRESA V TREH
      &ST1  &6F(0:2)  &t        & INSTRUKCIYAH V
      &ST1  &7F(0:2)  &t        & OSNOVNOM CIKLE.
      &ENN1 &-N, 4    &t        & $|rIl|\asg N-h$.
      &ST1  &4F(0:2)  &T
      &ENT1 &1-N, 4   &T        & $j\asg h+1$.
2H    &LDA  &INPUT+N,1&NT-S     & D3. uSTANOVITX $i$, $K$, $R$.
4H    &ENT2 &N-H,1    &NT-S     & $i\asg j-h$. (iZMENYAEMAYA INSTRUKCIYA)
5n    &smra &INPUT,2  &B+NT-S-A & D4. sRAVNITX $K$, $K_i$.
      &JOE  &7F       &B+NT-S-A & k SHAGU D6, ESLI $K\ge K_i$.
      &LDX  &INPUT,2  &B        & D5. pEREMESTITX  $R_i$, UMENXSHITX $i$.
6n    &STX  &INPUT+H,2&v        & $R_{i+h}\asg R_i$. (iZMENYAEMAYA INSTRUKCIYA)
      &DEC2 &0,4      &v        & $i\asg i-h$.
      &J2P  &5v       &v        & k SHAGU D4, ESLI $i>0$.
7n    &STA  &INPUT+H,2&NT-S     & D6. $R$ NA MESTO $R_{i+h}$. (iZMENYAEMAYA INSTRUKCIYA)
8n    &INC1 &1        &NT-S     & $j\asg j+1$.
      &J1NP &2v       &NT-S     & k D3, ESLI $j\le N$.
      &DEC3 &1        &t
      &J3P  &1v       &t        & $t\ge s\ge 1$.
\endcode
\progend

%% 108

\section *aNALIZ METODA shELLA. chTOBY VYBRATX HOROSHUYU POSLEDOVATELXNOSTX 
SHAGOV SORTIROVKI DLYA ALGORITMA D, NUZHNO PROANALIZIROVATX VREMYA RABOTY 
KAK FUNKCIYU OT |TIH SHAGOV. eTO PRIVODIT K OCHENX KRASIVYM, NO ESHCHE NE DO 
KONCA RESHENNYM MATEMATICHESKIM ZADACHAM; NIKOMU DO SIH POR NE UDALOSX 
NAJTI NAILUCHSHUYU VOZMOZHNUYU POSLEDOVATELXNOSTX SHAGOV DLYA BOLXSHIH $N$. tEM 
NE MENEE IZVESTNO DOVOLXNO MNOGO INTERESNYH FAKTOV O POVEDENII SORTIROVKI 
METODOM shELLA S UBYVAYUSHCHIM SHAGOM, I MY ZDESX IH KRATKO IZLOZHIM; PODROBNOSTI 
MOZHNO NAJTI V PRIVEDENNYH NIZHE UPRAZHNENIYAH. [chITATELYAM, NE IMEYUSHCHIM 
SKLONNOSTI K MATEMATIKE, LUCHSHE PROPUSTITX SLEDUYUSHCHIE NESKOLXKO STRANIC, 
DO FORMUL (8).]

sCHETCHIKI CHASTOT VYPOLNENIYA V PROGRAMME D POKAZYVAYUT, CHTO NA VREMYA 
VYPOLNENIYA VLIYAYUT PYATX FAKTOROV: RAZMER FAJLA $N$, CHISLO PROSMOTROV (T.E. 
CHISLO SHAGOV) $T=t$, SUMMA SHAGOV
$$
S=h_1+\cdots+h_t,
$$
CHISLO SRAVNENIJ $B+NT-S-A$ I CHISLO PEREMESHCHENIJ $B$. kAK I PRI ANALIZE 
PROGRAMMY S, ZDESX $A$ RAVNO CHISLU LEVOSTORONNIH MINIMUMOV, 
VSTRECHAYUSHCHIHSYA PRI PROMEZHUTOCHNYH OPERACIYAH SORTIROVKI, A $B$ RAVNO CHISLU 
INVERSIJ V PODFAJLAH. oSNOVNYM FAKTOROM, OT KOTOROGO ZAVISIT VREMYA RABOTY, 
YAVLYAETSYA VELICHINA $B$, PO|TOMU NA NEE MY I OBRATIM GLAVNYM OBRAZOM SVOE 
VNIMANIE. pRI ANALIZE BUDET PREDPOLAGATXSYA, CHTO KLYUCHI RAZLICHNY I 
PERVONACHALXNO RASPOLOZHENY V SLUCHAJNOM PORYADKE.

nAZOVEM OPERACIYU SHAGA D2 "$h$-SORTIROVKOJ". tOGDA SORTIROVKA METODOM 
shELLA SOSTOIT IZ $h_t$-SORTIROVKI, ZA KOTOROJ SLEDUET $h_{t-1}$-SORTIROVKA,
 \dots, ZA KOTOROJ SLEDUET $h_1$-SORTIROVKA. fAJL, V KOTOROM $K_i\le 
K_{i+h}$ PRI $1\le i \le N-h$, BUDEM NAZYVATX  $h\hbox{-UPORYADOCHENNYM}$.

rASSMOTRIM SNACHALA PROSTEJSHEE OBOBSHCHENIE PROSTYH VSTAVOK, KOGDA IMEYUTSYA 
VSEGO DVA SHAGA $h_2=2$ I $h_1=1$. vO VREMYA VTOROGO PROSMOTRA IMEEM 
2-UPORYADOCHENNUYU POSLEDOVATELXNOSTX KLYUCHEJ $K_1$ $K_2$ \dots $K_N$. lEGKO 
VIDETX, CHTO CHISLO PERESTANOVOK $a_1$ $a_2$~\dots $a_n$ MNOZHESTVA $\{1, 2, 
\ldots, P\}$, TAKIH, CHTO $a_i\le a_{i+2}$ PRI $l\le i \le n-2$, RAVNO
$$
\perm{n}{\floor{n/2}},
$$
TAK KAK SUSHCHESTVUET VSEGO ODNA 2-UPORYADOCHENNAYA PERESTANOVKA DLYA KAZHDOGO 
VYBORA $\floor{n/2}$ |LEMENTOV, RASPOLOZHENNYH V CHETNYH POZICIYAH $a_2a_4$, 
\dots, TOGDA OSTALXNYE $\ceil{n/2}$ |LEMENTOV POPADAYUT V POZICII S 
NECHETNYMI NOMERAMI. pOSLE 2-SORTIROVKI SLUCHAJNOGO FAJLA S ODINAKOVOJ 
VEROYATNOSTXYU MOZHET POLUCHITXSYA LYUBAYA 2-UPORYADOCHENNAYA PERESTANOVKA. kAKOVO 
SREDNEE CHISLO INVERSIJ VO VSEH TAKIH PERESTANOVKAH?
%% 109
\bye