\input style
\chapnotrue
\chapno=5
\subchno=2
\subsubchno=1
%% 130

\excercises
\ex[m25]\exhead(bESPORYADOK V BIBLIOTEKE.) nEBREZHNYE CHITATELI CHASTO 
STAVYAT KNIGI NA POLKI V BIBLIOTEKE NE NA SVOE MESTO. oDIN IZ SPOSOBOV 
IZMERITX STEPENX BESPORYADKA V BIBLIOTEKE---POSMOTRETX, KAKOE MINIMALXNOE, 
KOLICHESTVO RAZ PRISHLOSX BY BRATX KNIGU S ODNOGO MESTA I VSTAVLYATX EE V 
DRUGOE MESTO DO TEH POR, POKA KNIGI NE OKAZHUTSYA RASPOLOZHENNYMI V PRAVILXNOM 
PORYADKE.

pUSTX $\pi=a_1\ a_2\ \ldots\ a_n$---PERESTANOVKA MNOZHESTVA 
$\{1, 2, \ldots, n\}$. "oPERACIYA UDALENIYA-VSTAVKI" ZAMENYAET $\pi$ NA
$$
a_1\ a_2\ \ldots\ a_{i-1}\ \ldots\ a_j\ a_i\ a_{j+1}\ \ldots\ a_n
$$
ILI NA
$$
a_1\ \ldots\ a_j\ a_i\ a_{j+1}\ \ldots\ a_{i-1}\ a_{i+1}\ \ldots\ a_n
$$
PRI NEKOTORYH $i$ I $j$. pUSTX $\mathop{\rm dis}\nolimits 
(\pi)$---MINIMALXNOE CHISLO OPERACIJ UDALENIYA-VSTAVKI, NEOBHODIMOE DLYA 
UPORYADOCHENIYA PERESTANOVKI $\pi$. mOZHNO LI VYRAZITX $\mathop{\rm 
dis}\nolimits (\pi)$ CHEREZ BOLEE PROSTYE HARAKTERISTIKI $\pi$?

\ex[40] pROVEDITE |KSPERIMENTY SO SLEDUYUSHCHEJ MODIFIKACIEJ SORTIROVKI S 
UBYVAYUSHCHIM SHAGOM, IMEYUSHCHEJ CELXYU USKORENIE "VNUTRENNEGO CIKLA": DLYA $s=t$, 
$t-1$, \dots, $2$ I DLYA $j=h_s+1$, $h_s+2$, \dots, $N$ POMENYATX 
MESTAMI $R_{j-h_s}\xchg R_j$, ESLI $K_{j-h_s}>K_j$. (tAKIM OBRAZOM, 
REZULXTAT OBMENOV NE RASPROSTRANYAETSYA; NE PROIZVODITSYA SRAVNENIJ 
$K_{j-h_s}:K_{j-2h_s}$. zAPISI NE OBYAZATELXNO BUDUT $h_s$-OTSORTIROVANY, 
NO |TI PREDVARITELXNYE PROSMOTRY SPOSOBSTVUYUT SOKRASHCHENIYU CHISLA 
INVERSIJ.) sORTIROVKA ZAVERSHAETSYA PRIMENENIEM PROSTYH VSTAVOK.
\subsubchap{oBMENNAYA SORTIROVKA}
mY PODOSHLI TEPERX KO VTOROMU IZ SEMEJSTV ALGORITMOV SORTIROVKI, 
UPOMYANUTYH V SAMOM NACHALE \S~5.2,---K METODAM "OBMENOV" ILI "TRANSPOZICIJ", 
PREDUSMATRIVAYUSHCHIH SISTEMATICHESKIJ OBMEN MESTAMI MEZHDU |LEMENTAMI PAR, V 
KOTORYH NARUSHAETSYA UPORYADOCHENNOSTX, DO TEH POR, POKA TAKIH PAR NE OSTANETSYA.

pROCESS PROSTYH VSTAVOK (ALGORITM 5.2.1S) MOZHNO RASSMATRIVATX KAK 
OBMENNUYU SORTIROVKU: MY BEREM NOVUYU ZAPISX $R_j$ I, PO SUSHCHESTVU, MENYAEM 
MESTAMI S SOSEDYAMI SLEVA DO TEH POR, POKA ONA NE ZAJMET NUZHNOGO MESTA. 
tAKIM OBRAZOM, KLASSIFIKACIYA METODOV SORTIROVKI PO TAKIM SEMEJSTVAM, 
KAK "VSTAVKI", "OBMENY", "VYBOR" I T. D., NE VSEGDA CHETKO OPREDELENA. v 
|TOM PUNKTE MY RASSMOTRIM CHETYRE TIPA METODOV SORTIROVKI, DLYA KOTORYH 
OBMENY YAVLYAYUTSYA OSNOVNOJ HARAKTERISTIKOJ: 
\emph{OBMENNUYU SORTIROVKU S VYBOROM} ("METOD PUZYRXKA"), 
\emph{OBMENNUYU SORTIROVKU SO SLIYANIEM} (PARALLELXNUYU SORTIROVKU b|TCHERA), 
\emph{OBMENNUYU SORTIROVKU S RAZDELENIEM} ("BYSTRUYU SORTIROVKU" hOARA), 
\emph{PORAZRYADNUYU OBMENNUYU SORTIROVKU}.

\section mETOD PUZYRXKA. pOZHALUJ, NAIBOLEE OCHEVIDNEJ SPOSOB OBMENNOJ 
SORTIROVKI |TO SRAVNIVATX $K_1$ S $K_2$, MENYAYA MESTAMI $R_1$ I $R_2$, ESLI 
IH KLYUCHI NE UPORYADOCHENY, ZATEM PRODELATX TO ZHE SAMOE S $R_2$ I $R_3$, 
$R_3$ I $R_4$ I T. D. pRI VYPOLNENII |TOJ POSLEDOVATELXNOSTI OPERACIJ 
ZAPISI S BOLXSHIMI KLYUCHAMI BUDUT PRODVIGATXSYA VPRAVO, I NA SAMOM DELE 
ZAPISX S NAIBOLXSHIM KLYUCHOM 
%% 131
ZAJMET POLOZHENIE $R_N$. pRI MNOGOKRATNOM VYPOLNENII |TOGO PROCESSA 
SOOTVETSTVUYUSHCHIE ZAPISI POPADUT V POZICII $R_{N-1}$, $R_{N-2}$ I T. D., TAK 
CHTO V KONCE KONCOV VSE ZAPISI BUDUT UPORYADOCHENY.

nA RIS.~14 POKAZANO DEJSTVIE |TOGO METODA SORTIROVKI NA SHESTNADCATI KLYUCHAH 
503 087 512 \dots 703. fAJL CHISEL UDOBNO
\picture{rIS. 14.  sORTIROVKA METODOM PUZYRXKA V DEJSTVII.}
PREDSTAVLYATX NE GORIZONTALXNO, A VERTIKALXNO, CHTOBY ZAPISX $R_N$ BYLA 
SVERHU, a $R_1$---SNIZU. mETOD NAZVAN "METODOM PUZYRXKA", POTOMU CHTO 
BOLXSHIE |LEMENTY, PODOBNO PUZYRXKAM, "VSPLYVAYUT" NA SOOTVETSTVUYUSHCHUYU 
POZICIYU V PROTIVOPOLOZHNOSTX "METODU POGRUZHENIYA" (T. E. METODU PROSTYH 
VSTAVOK), V KOTOROM |LEMENTY POGRUZHAYUTSYA NA SOOTVETSTVUYUSHCHIJ UROVENX. mETOD 
PUZYRXKA IZVESTEN TAKZHE POD BOLEE PROZAICHESKIMI IMENAMI, TAKIMI, 
KAK "OBMENNAYA SORTIROVKA S VYBOROM" ILI METOD "RASPROSTRANENIYA". nETRUDNO 
VIDETX, CHTO POSLE KAZHDOGO PROSMOTRA FAJLA VSE ZAPISI, NACHINAYA S SAMOJ 
POSLEDNEJ, KOTORAYA UCHASTVOVALA V OBMENE,
%%132
I VYSHE, DOLZHNY ZANYATX SVOJ OKONCHATELXNYE POZICII,TAK CHTO IH NE NUZHNO 
PROVERYATX PRI POSLEDUYUSHCHIH PROSMOTRAH. nA RIS.~14 TAKOGO RODA PRODVIZHENIYA 
ALGORITMA OTMECHENY CHERTOCHKAMI. zAMETIM, NAPRIMER, CHTO POSLE CHETVERTOGO 
PROSMOTRA STALO IZVESTNO, CHTO ESHCHE PYATX ZAPISEJ ZANYALI SVOI OKONCHATELXNYE 
POZICII. pRI POSLEDNEM, PROSMOTRE VOOBSHCHE NE BYLO PROIZVEDENO 
OBMENOV. tEPERX, SDELAV |TI NABLYUDENIYA, MY GOTOVY SFORMULIROVATX ALGORITM.

\alg v.(mETOD PUZYRXKA.) 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[nACHALXNAYA USTANOVKA BOUND.] uSTANOVITX 
$|BOUND|\asg N$. (|BOUND|---INDEKS SAMOGO VERHNEGO |LEMENTA, O KOTOROM ESHCHE 
NE IZVESTNO, ZANYAL LI ON UZHE SVOYU OKONCHATELXNUYU POZICIYU; TAKIM OBRAZOM, MY 
OTMECHAEM, CHTO K |TOMU MOMENTU ESHCHE NICHEGO NE IZVESTNO.)

\st[cIKL PO $j$.] uSTANOVITX $t\asg0$. vYPOLNITX SHAG \stp{z} PRI $j=1$, 2, 
\dots, $|BOUND|-1$. zATEM PEREJTI K SHAGU \stp{4}. (eSLI $|BOUND|=1$, TO 
SRAZU PEREJTI K \stp{4}.)

\st[sRAVNENIE/OBMEN $R_j : R_{j+1}$]%
\note{zDESX, KAK I RANEE, DVOETOCHIE ISPOLXZUETSYA DLYA OBOZNACHENIYA 
OPERATORA SRAVNENIYA.---{\sl pRIM. RED.}}).
eSLI $K_j>K_{j+1}$, TO POMENYATX MESTAMI  $R_j\xchg R_{j+1}$ I USTANOVITX 
$t\asg j$.

\st[bYLI LI OBMENY?] eSLI $t=0$, TO ZAVERSHITX RABOTU ALGORITMA. v 
PROTIVNOM SLUCHAE USTANOVITX $|BOUND|\asg t$ I VOZVRATITXSYA K SHAGU \stp{2}.
\algend
\picture{rIS. 15. bLOK-SHEMA SORTIROVKI METODOM PUZYRXKA.}

\prog v.(mETOD PUZYRXKA.) kAK I V PREDYDUSHCHIH \MIX-PROGRAMMAH |TOJ GLAVY, 
MY PREDPOLAGAEM, CHTO SORTIRUEMYE |LEMENTY NAHODYATSYA V YACHEJKAH 
$|INPUT|+1$, \dots,  $|INPUT|+N$;
REGISTRY: $|rI1|\equiv t$; $|rI2|\equiv j$.
%% 133
\code
START &ENT1 & N          & 1   & B1. nACHALXNAYA USTANOVKA |BOUND|.  $t\asg N$.
1H    &ST1  & BOUND (1:2)& A   & $|BOUND|\asg t$.
      &ENT2 & 1          & A   & v2. cIKL. PO $j$.
      &ENT1 & 0          & A   & $t \asg 0$.
      &JMP  & BOUND      & A   & vYHOD, ESLI  $j\ge |BOUND|$.
3H    &LDA  & INPUT, 2   & C   & B3. sRAVNENIE/OBMEN $R_j:R_{j+1}$.
      &smra & INPUT+1,2  & C 
      &JLE  & 2F         & C   & eSLI $K_j\le K_j+1$, TO BEZ OBMENA.
      &LDX  & INPUT+1,2  & B   & $R_{j+1}$
      &STX  & INPUT,2    & B   & $\to R_j$.
      &STA  & INPUT+1,2  & B   & $\hbox{(PREZHNEE $R_j$)}\to R_{j+1}$
      &ENT1 & 0,2        & B   & $t\asg j$.
9H    &INC2 & 1          & C   & $j\asg j+1$.
BOUND &ENTX & -*,2       & A+C & $|rX|\asg j-|BOUND|$. (iZMENYAEMAYA INSTRUKCIYA)
      &JXN  & 3v         & A+C & $1\le j <|BOUND|$.
4H    &J1P  & 1B         & A   & v4. bYLI LI OBMENY?  k v2, ESLI $t>0$.
\endcode
\progend

\section aNALIZ METODA PUZYRXKA. oCHENX POLEZNO ISSLEDOVATX VREMYA RABOTY 
ALGORITMA v. oNO OPREDELYAETSYA TREMYA VELICHINAMI: CHISLOM PROSMOTROV $A$, 
CHISLOM OBMENOV $B$ I CHISLOM SRAVNENIJ $C$. eSLI ISHODNYE KLYUCHI RAZLICHNY I 
RASPOLOZHENY V SLUCHAJNOM PORYADKE, TO MOZHNO PREDPOLOZHITX, CHTO ONI OBRAZUYUT 
SLUCHAJNUYU PERESTANOVKU MNOZHESTVA $\{1,2, \ldots, n\}$. pONYATIE TABLICY 
INVERSIJ (P.~5.1.1) PRIVODIT K PROSTOMU SPOSOBU OPISANIYA DEJSTVIYA 
KAZHDOGO PROSMOTRA PRI SORTIROVKE METODOM PUZYRXKA.

\proclaim tEOREMA I. pUSTX $a_1$ $a_2$ \dots\ $a_n$---PERESTANOVKA   
MNOZHESTVA $\{1, 2, \ldots, n\}$,  A $b_1$ $b_2$ \dots 
$b_n$---SOOTVETSTVUYUSHCHAYA TABLICA INVERSIJ. eSLI V REZULXTATE OCHEREDNOGO 
PROSMOTRA PRI SORTIROVKE METODOM PUZYRXKA (ALGORITM v) PERESTANOVKA $a_1$ 
$a_2$ \dots $a_n$ PREOBRAZUETSYA V $a'_1$ $a'_2$ \dots $a'_n$, TO 
SOOTVETSTVUYUSHCHAYA TABLICA INVERSIJ $b'_1$ $b'_2$ \dots $b'_n$ POLUCHAETSYA IZ 
$b_1$ $b_2$ \dots $b_n$ UMENXSHENIEM NA EDINICU KAZHDOGO NULEVOGO |LEMENTA.

\proof eSLI PERED $a_i$ IMEETSYA BOLXSHIJ |LEMENT, TO $a_i$ POMENYAETSYA 
MESTAMI S NAIBOLXSHIM IZ PREDSHESTVUYUSHCHIH |LEMENTOV, TAK CHTO $b_i$ 
UMENXSHITSYA NA EDINICU. s DRUGOJ STORONY, ESLI PERED $a_i$ NET |LEMENTA, 
BOLXSHEGO $a_i$, TO $a_i$ NIKOGDA NE POMENYAETSYA MESTAMI S BOLXSHIM |LEMENTOM,
TAK CHTO $b_{a_i}$ OSTANETSYA 0. 
\proofend

iTAK, MOZHNO RAZOBRATXSYA V TOM, CHTO PROISHODIT V PROCESSE SORTIROVKI 
METODOM PUZYRXKA, IZUCHAYA POSLEDOVATELXNOSTX TABLIC INVERSIJ MEZHDU 
PROSMOTRAMI. vOT KAK VYGLYADYAT, NAPRIMER,
%% 134
\bye
