\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