\input style
TABLICY INVERSIJ DLYA RIS.~14:
$$
\vcenter{\halign{
#\hfil\bskip&&\bskip$#$\bskip\cr
 & 3 & 1 & 8 & 3 & 4 & 5 & 0 & 4 & 0 & 3& 2 & 2 & 3 & 2 & 1 & 0\cr
pROSMOTR~1\cr
 & 2 & 0 & 7 & 2 & 3 & 4 & 0 & 3 & 0 & 2 & 1 & 1 & 2 & 1 & 0 & 0\cr
pROSMOTR~2\cr
 & 1 & 0 & 6 & 1 & 2 & 3 & 0 & 2 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0\cr
pROSMOTR~3\cr
 & 0 & 0 & 5 & 0 & 1 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
}}
\eqno  (1)
$$
I~T.~D. pO|TOMU, ESLI~$b_1\,b_2\,\ldots\,b_n$---TABLICA INVERSIJ 
ISHODNOJ PERESTANOVKI, TO DOLZHNY VYPOLNYATXSYA RAVENSTVA
$$
\eqalignno{
A&=1+\max(b_1, b_2,\ldots, b_n); & (2) \cr
B&=b_1+b_2+\cdots+b_n; & (3) \cr
C&=c_1+c_2+\cdots+c_A, & (4) \cr
}
$$
GDE~$c_j$---ZNACHENIE~$|BOUND|-1$ PERED NACHALOM 
$j\hbox{-GO}$~PROSMOTRA. iSPOLXZUYA TABLICY INVERSIJ, ZAPISHEM
$$
c_j=\max\set{ b_i+i \mid b_i\ge j-1}-j
\eqno(5)
$$
(SM.~UPR.~5). sLEDOVATELXNO, V PRIMERE~(1) $A=9$, $B=41$, 
$C=15+14+13+12+7+5+4+3+2=75$. oBSHCHEE VREMYA SORTIROVKI NA MASHINE \MIX{} DLYA 
RIS.~14 RAVNO~$1030u$.

rASPREDELENIE VELICHINY~$B$ (SUMMARNOE CHISLO INVERSIJ V SLUCHAJNOJ 
PERESTANOVKE) NAM UZHE HOROSHO IZVESTNO; TAKIM OBRAZOM, OSTAETSYA 
PROANALIZIROVATX VELICHINY~$A$ I~$C$.

vEROYATNOSTX TOGO, CHTO~$A\le k$, RAVNA PROIZVEDENIYU~$1/n!$ NA CHISLO TABLIC 
INVERSIJ, NE SODERZHASHCHIH KOMPONENT~$\ge k$, IMENNO~$k^{n-k}k!$ 
PRI~$1\le k \le n$. sLEDOVATELXNO, VEROYATNOSTX TOGO, CHTO POTREBUETSYA ROVNO 
$k$~PROSMOTROV, RAVNA
$$
A_k={1\over n!}(k^{n-k}k!-(k-1)^{n-k+1}(k-1)!).
\eqno(6)
$$
tEPERX MOZHNO VYCHISLITX SREDNEE ZNACHENIE~$\sum k A_k$, 
PROIZVODYA SUMMIROVANIE PO CHASTYAM, POLUCHAEM
$$
A_{ave}=n+1\sum_{0\le k \le n} -{k^{n-k}k!\over n!}=n+1+P(n),
\eqno(7)
$$
GDE~$P(n)$---FUNKCIYA, ASIMPTOTICHESKOE POVEDENIE KOTOROJ, KAK BYLO POKAZANO V 
P.~1.2.11, OPISYVAETSYA FORMULOJ~$\sqrt{\pi n/2}-{2\over3}+O(1/\sqrt{n})$. 
fORMULA~(7) BYLA NAJDENA BEZ DOKAZATELXSTVA
e.~X.~fR|NDOM [{\sl JACM,\/} {\bf 3} (1956), 150]; DOKAZATELXSTVO V 
SVOEJ DOKTORSKOJ DISSERTACII PRIVEL gOVARD~b.~dEMUT 
[(Stanford University: October, 1956), 64--68]. sTANDARTNOE 
OTKLONENIE VELICHINY~$A$ SM.~V~UPR.~7.

%% 135

sUMMARNOE CHISLO SRAVNENIJ~$C$ ISSLEDOVATX NESKOLXKO SLOZHNEE, I MY 
RASSMOTRIM TOLXKO~$C_{ave}$. pUSTX~$f_j(k)$---CHISLO TAKIH TABLIC 
INVERSIJ~$b_1\,\ldots\,b_n$ ($n$~FIKSIROVANO), CHTO PRI~$1\le i \le n$ 
LIBO~$b_i<j-1$, LIBO~$b_i+i-j\le k$; TOGDA
$$
f_j(k)=(j+k)! (j-1)^{n-j-k} \rem{PRI~$0\le k \le n-j$.}
\eqno (8)
$$
(sM.~UPR.~8.) sREDNEE ZNACHENIE~$c_j$ V~(5) RAVNO~$\sum 
k(f_j(k)-f_j(k-1)))/n!$; SUMMIRUYA PO CHASTYAM, A ZATEM PO~$j$, POLUCHAEM FORMULU
$$
C_{ave}=\perm{n+1}{2}-{1\over n!}
\sum_{\scriptstyle 1\le j \le n \atop \scriptstyle 0\le k \le n-j} f_j(k)=
\perm{n+1}{2}-{1\over n!}\sum_{0\le r < s \le n} s! r^{n-s}.
\eqno(9)
$$
oPREDELITX ASIMPTOTICHESKOE ZNACHENIE ZDESX NE TAK PROSTO, I  MY VERNEMSYA K 
NEMU V KONCE |TOGO PUNKTA.

chTOBY PODVESTI ITOG NASHEGO ANALIZA METODA PUZYRXKA, ZAPISHEM FORMULY, 
VYVEDENNYE VYSHE (A TAKZHE NIZHE), SLEDUYUSHCHIM OBRAZOM:
$$
\eqalignno{
A&=(\min 1, \ave N-\sqrt{\pi N/2}+O(1), \max N); & (10) \cr
B&=(\min 0, \ave {1\over4}(N^2-N), \max{1\over 2}(N^2-N)); & (11) \cr
C&=\left(\min N-1, \ave{1\over 2}(N^2-N\ln N-(\gamma+\ln 2-1)N)+O(\sqrt{N}),
   \max {1\over 2}(N^2-N)\right). & (12) \cr
}
$$
vO VSEH SLUCHAYAH MINIMUM DOSTIGAETSYA, KOGDA ISHODNYJ FAJL UZHE UPORYADOCHEN, A 
MAKSIMUM---KOGDA ZAPISI RASPOLOZHENY V OBRATNOM PORYADKE; TAKIM OBRAZOM, 
VREMYA RABOTY DLYA MASHINY~\MIX{} 
RAVNO~$8A+7B+8C+1=(\min 8N+1, \ave 5.75N^2+O(N \ln N), \max 7.5N^2+0.5N+1)$.

\section uSOVERSHENSTVOVANIYA METODA PUZYRXKA. mY POTRATILI MNOGO USILIJ NA 
ANALIZ METODA PUZYRXKA, I, HOTYA SPOSOBY, PRIMENYAVSHIESYA PRI VYCHISLENIYAH, 
POUCHITELXNY, REZULXTATY RAZOCHAROVYVAYUT, POSKOLXKU ONI GOVORYAT O TOM, CHTO 
METOD PUZYRXKA VOVSE NE TAK UZH HOROSH. pO SRAVNENIYU S PROSTYMI VSTAVKAMI 
(ALGORITM~5.2.1S) METOD PUZYRXKA OPISYVAETSYA BOLEE SLOZHNOJ PROGRAMMOJ 
I TREBUET PRIMERNO V 2~RAZA BOLXSHE VREMENI!

mOZHNO PREDLOZHITX NESKOLXKO PUTEJ ULUCHSHENIYA METODA PUZYRXKA. nAPRIMER, NA 
RIS.~14 PERVOE SRAVNENIE V 4-M PROSMOTRE IZLISHNE, TAK ZHE KAK I PERVYE DVA 
SRAVNENIYA V 5-M PROSMOTRE I PERVYE TRI V 6-M I 7-M PROSMOTRAH. zAMETIM 
TAKZHE, CHTO ZA ODIN PROSMOTR |LEMENT NE MOZHET PEREMESTITXSYA BOLEE CHEM 
NA ODNU POZICIYU VLEVO; TAK CHTO ESLI NAIMENXSHIJ |LEMENT VNACHALE
%%136
NAHODILSYA V PRAVOM KONCE, TO MY VYNUZHDENY VYPOLNITX MAKSIMALXNOE CHISLO 
SRAVNENIJ. eTO NAVODIT NA MYSLX O "SHEJKER-SORTIROVKE", KOGDA FAJL 
PROSMATRIVAETSYA POPEREMENNO V OBOIH NAPRAVLENIYAH (RIS.~16). pRI TAKOM 
PODHODE SREDNEE CHISLO SRAVNENIJ NESKOLXKO SOKRASHCHAETSYA. k.~e.~aJVERSON [A 
Programming Language (Wiley, 1962), 218--219] SDELAL INTERESNOE V |TOM 
OTNOSHENII NABLYUDENIE: ESLI~$j$---TAKOJ INDEKS, CHTO~$R_j$ I~$R_{j+1}$ NE 
MENYAYUTSYA MESTAMI PRI DVUH POSLEDOVATELXNYH PROSMOTRAH
\picture{rIS.~16.  "shEJKER-SORTIROVKA".}
V PROTIVOPOLOZHNYH NAPRAVLENIYAH, TO ZAPISI~$R_j$ I~$R_{j+1}$ 
DOLZHNY ZANIMATX SVOI OKONCHATELXNYE POZICII, I ONI MOGUT NE UCHASTVOVATX V 
POSLEDUYUSHCHIH SRAVNENIYAH. nAPRIMER, PROSMATRIVAYA PERESTANOVKU 
$4\,3\,2\,1\,8\,6\,9\,7\,5$ SLEVA NAPRAVO, POLUCHAEM $3\,2\,1\,4\,6\,8\,7\,5\,9$: 
ZAPISI~$R_4$ I~$R_5$ NE POMENYALISX MESTAMI. pRI PROSMOTRE POSLEDNEJ 
PERESTANOVKI SPRAVA NALEVO $R_4$ VSE ESHCHE MENXSHE (NOVOJ) ZAPISI~$R_5$; 
SLEDOVATELXNO, MOZHNO SRAZU ZHE SDELATX VYVOD O TOM, CHTO ZAPISI~$R_4$ 
I~$R_5$ MOGUT I NE UCHASTVOVATX NI V ODNOM IZ POSLEDUYUSHCHIH, SRAVNENIJ.

oDNAKO NI ODNO IZ |TIH USOVERSHENSTVOVANIJ NE PRIVODIT K LUCHSHEMU ALGORITMU, 
CHEM ALGORITM SORTIROVKI PROSTYMI VSTAVKAMI,
%%137
A MY UZHE ZNAEM, CHTO DAZHE ON NE GODITSYA PRI BOLXSHIH~$N$. dRUGAYA IDEYA 
SOSTOIT V TOM, CHTOBY IZBEZHATX BOLXSHINSTVA OBMENOV. tAK KAK BOLXSHAYA CHASTX 
|LEMENTOV VO VREMYA OBMENOV PROSTO SDVIGAETSYA NA ODIN SHAG VLEVO, TO MOZHNO 
BYLO BY DOSTICHX TOGO ZHE |FFEKTA, INACHE RASSMATRIVAYA MASSIV---SMESTIV 
NACHALO OTSCHETA! nO POLUCHENNYJ ALGORITM NE PREVOSHODIT METODA PROSTOGO 
\emph{VYBORA} (ALGORITM~5.2.3S), KOTORYJ MY IZUCHIM POZZHE.

kOROCHE GOVORYA, METOD PUZYRXKA, KAZHETSYA, NE OBLADAET NIKAKIMI 
DOSTOINSTVAMI, ZA KOTORYE EGO MOZHNO BYLO BY POREKOMENDOVATX, ESLI NE 
SCHITATX LEGKO ZAPOMINAYUSHCHEGOSYA NAZVANIYA I INTERESNYH TEORETICHESKIH ZADACH, K 
KOTORYM ON PRIVODIT.

\section pARALLELXNAYA SORTIROVKA b|TCHERA. eSLI MY HOTIM POLUCHITX ALGORITM 
OBMENNOJ SORTIROVKI, VREMYA RABOTY KOTOROGO IMEET PORYADOK, MENXSHIJ~$N^2$, 
TO NEOBHODIMO PODBIRATX DLYA SRAVNENIJ NEKOTORYE PARY \emph{NESOSEDNIH} 
KLYUCHEJ~$(K_i, K_j)$; INACHE PRIDETSYA
\picture{rIS.~17. aLGORITM~M.}
VYPOLNITX STOLXKO OBMENOV, SKOLXKO INVERSIJ IMEETSYA V ISHODNOJ 
PERESTANOVKE, A SREDNEE CHISLO INVERSIJ RAVNO~$(N^2-N)/4$. v 1964~G.\ 
k.~e.~b|TCHER 
[Proc. AFIPS Spring Joint Computer Conference, {\bf 32} (1968), 307--314]
OTKRYL ODIN ISKUSNYJ SPOSOB ZAPROGRAMMIROVATX POSLEDOVATELXNOSTX 
SRAVNENIJ, PREDNAZNACHENNUYU DLYA OTYSKANIYA VOZMOZHNYH OBMENOV. eGO METOD 
DALEKO NE OCHEVIDEN. v SAMOM DELE, TOLXKO DLYA TOGO, CHTOBY POKAZATX EGO 
SPRAVEDLIVOSTX, TREBUETSYA VESXMA SLOZHNOE DOKAZATELXSTVO, TAK KAK 
VYPOLNYAETSYA, OTNOSITELXNO MALO SRAVNENIJ. mY OBSUDIM DVA DOKAZATELXSTVA, 
ODNO V |TOM PUNKTE I ODNO V P.~5.3.4.

sHEMA SORTIROVKI b|TCHERA NESKOLXKO NAPOMINAET SORTIROVKU shELLA, NO 
SRAVNENIYA VYPOLNYAYUTSYA PO-NOVOMU, TAK CHTO RASPROSTRANENIE OBMENOV NE 
OBYAZATELXNO. tAK, MOZHNO SRAVNITX TABL.~1 S TABL.~5.2.1-3. sORTIROVKA 
b|TCHERA DEJSTVUET KAK 8-SORTIROVKA, 4-SORTIROVKA, 2-SORTIROVKA I 
1-SORTIROVKA, NO SRAVNENIYA NE
%%138
PEREKRYVAYUTSYA. tAK KAK V ALGORITME b|TCHERA, PO SUSHCHESTVU, PROISHODIT 
SLIYANIE PAR OTSORTIROVANNYH PODPOSLEDOVATELXNOSTEJ, TO EGO MOZHNO NAZVATX 
"OBMENNOJ SORTIROVKOJ SO SLIYANIEM".

\alg M.(oBMENNAYA SORTIROVKA SO SLIYANIEM.) 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$.  pREDPOLAGAETSYA, CHTO~$N\ge2$.

\st[nACHALXNAYA USTANOVKA~$p$.] uSTANOVITX~$p\asg 2^{t-1}$, 
GDE~$t=\ceil{\log_2 N}$---NAIMENXSHEE CELOE CHISLO, TAKOE, CHTO~$2^t\ge N$. 
(shAGI~\stp{2},~\dots, \stp{5} BUDUT VYPOLNYATXSYA S~$p=2^{t-1}$, 
$2^{t-2}$,~\dots, $1$.)

\st[nACHALXNAYA USTANOVKA~$q$, $r$, $d$.] uSTANOVITX~$q\asg 2^{t-1}$, $r\asg 0$, 
$d\asg p$.

\st[cIKL PO~$t$.] dLYA VSEH~$t$, TAKIH, CHTO~$0\le i < N-d$ I~$i\land p=r$,
VYPOLNITX SHAG~\stp{4}. zATEM PEREJTI K SHAGU~\stp{5}. (zDESX CHEREZ~$i\land p$ 
OBOZNACHENA OPERACIYA "LOGICHESKOE I" NAD DVOICHNYMI PREDSTAVLENIYAMI 
CHISEL~$i$ I~$p$; VSE BITY REZULXTATA RAVNY~$0$, KROME TEH, DLYA KOTORYH V 
SOOTVETSTVUYUSHCHIH POZICIYAH~$i$ I~$p$ NAHODYATSYA EDINICHNYE BITY. 
tAK, $13\land 21=(1101)_2\land (10101)_2=(00101)_2=5$. k |TOMU 
MOMENTU~$d$---NECHETNOE KRATNOE~$p$ (T.~E.\ CHASTNOE OT DELENIYA~$d$ NA~$p$ 
NECHETNO), A~$p$---STEPENX DVOJKI, TAK CHTO~$i\land p \ne (i+d)\land p$; 
OTSYUDA SLEDUET, CHTO DEJSTVIYA SHAGA~\stp{4} MOZHNO VYPOLNYATX PRI VSEH 
NUZHNYH ZNACHENIYAH~$i$ V LYUBOM PORYADKE ILI DAZHE ODNOVREMENNO.)

\st[sRAVNENIE/OBMEN~$R_{i+1}:R_{i+d+1}$.] eSLI~$K_{i+1}>K_{i+d+1}$,  TO 
POMENYATX MESTAMI~$R_{i+1}\xchg R_{i+d+1}$.

\st[cIKL PO~$q$.] eSLI~$q\ne p$, TO USTANOVITX~$d\asg q-p$, $q\asg q/2$,
$r\asg p$ I VOZVRATITXSYA K SHAGU~\stp{3}.

\st[cIKL PO~$p$.] (k |TOMU MOMENTU PERESTANOVKA~$K_1\,K_2\,\ldots\,K_N$ 
BUDET $p$-UPORYADOCHENA.) uSTANOVITX~$p\asg \floor{p/2}$. eSLI~$p>0$, 
TO VOZVRATITXSYA K SHAGU~\stp{2}.
\algend

v TABL.~1 |TOT METOD PROILLYUSTRIROVAN PRI~$N=16$. zAMETIM, CHTO ALGORITM 
SORTIRUET $N$~|LEMENTOV, PO SUSHCHESTVU, PUTEM NEZAVISIMOJ SORTIROVKI 
PODFAJLOV~$R_1$, $R_3$, $R_5$,~\dots{} I~$R_2$, $R_4$, $R_6$,~\dots, POSLE 
CHEGO VYPOLNYAYUTSYA SHAGI~M2,~\dots, M5 S~$p=1$, CHTOBY SLITX DVE 
OTSORTIROVANNYE POSLEDOVATELXNOSTI.

chTOBY DOKAZATX, CHTO MAGICHESKAYA POSLEDOVATELXNOSTX SRAVNENIJ/OBMENOV, 
OPISANNAYA V ALGORITME~M, DEJSTVITELXNO SORTIRUET LYUBOJ 
FAJL~$R_1\,R_2\,\ldots\,R_N$, MY DOLZHNY POKAZATX TOLXKO, CHTO V REZULXTATE 
VYPOLNENIYA SHAGOV OT~M2 DO~M5 S~$p=1$ BUDET SLIT LYUBOJ 2-UPORYADOCHENNYJ 
FAJL~$R_1\,R_2\,\ldots\,R_N$. dLYA |TOJ CELI MOZHNO VOSPOLXZOVATXSYA METODOM 
RESHETOCHNYH DIAGRAMM IZ P.~5.2.1 (SM.~RIS.~11); KAZHDAYA 2-UPORYADOCHENNAYA 
PERESTANOVKA MNOZHESTVA~$\set{1, 2,~\ldots, N}$ SOOTVETSTVUET NA RESHETKE 
EDINSTVENNOMU PUTI IZ VERSHINY~$(0,0)$ V~$(\ceil{N/2}, \floor{N/2})$. 
nA RIS.~18(A) POKAZAN
%%139
\picture{tABLICA~1. p.139}
PRIMER PRI~$N=16$, SOOTVETSTVUYUSHCHIJ PERESTANOVKE 
$1\,3\,2\,4\,10\,5\,11\,6\,13\,7\,14\,8\,15\,9\,16\,12$. 
dEJSTVIE SHAGA~M3 PRI~$p=1$, $q=2^{t-1}$, 
$r=0$, $d=1$ SOSTOIT V SRAVNENII (I, VOZMOZHNO, OBMENE) ZAPISEJ~$R_1:R_2$, 
$R_3:R_4$ I~T.~D. eTOJ OPERACII SOOTVETSTVUET PROSTOE PREOBRAZOVANIE 
RESHETOCHNOGO PUTI: "PEREGIB" OTNOSITELXNO DIAGONALI, ESLI NEOBHODIMO, TAK,
CHTOBY PUTX NIGDE NE PROHODIL VYSHE DIAGONALI. (sM.~RIS.~18(b) I 
DOKAZATELXSTVO V UPR.~10.) dEJSTVIE POSLEDUYUSHCHIH POVTORENIJ SHAGA~M3 
S~$p=r=1$ I~$d=2^{t-1}-1$, $2^{t-2}-1$,~\dots, $1$ SOSTOIT V 
SRAVNENII/OBMENE ZAPISEJ~$R_2:R_{2+d}$, $R_4:R_{4+d}$ I~T.~D., I OPYATX 
IMEETSYA PROSTAYA GEOMETRICHESKAYA INTERPRETACIYA: PUTX "PEREGIBAETSYA" 
OTNOSITELXNO PRYAMOJ, RASPOLOZHENNOJ NA $(d+l)/2$~EDINIC NIZHE DIAGONALI 
(SM.~RIS.~18(c) I~(d)). v KONCE KONCOV PRIHODIM K PUTI, IZOBRAZHENNOMU NA 
RIS.~18(e), KOTORYJ SOOTVETSTVUET POLNOSTXYU OTSORTIROVANNOJ 
PERESTANOVKE. nA |TOM "GEOMETRICHESKOE DOKAZATELXSTVO" SPRAVEDLIVOSTI ALGO-
%%140
\bye