\input style \chapnotrue \chapno=5\subchno=2\subsubchno=3 %% 188 pUSTX $s_l$---RAZMER PODDEREVA S KORNEM~$l$, A~$M_N$---MULXTIMNOZHESTVO~$\{s_1, s_2, \ldots, s_N\}$ VSEH |TIH RAZMEROV. iSPOLXZUYA (14) I (15), LEGKO VYCHISLITX~$M_N$ PRI LYUBOM ZADANNOM~$N$. v UPR.~5.1.4--20 POKAZANO, CHTO OBSHCHEE CHISLO SPOSOBOV POSTROITX PIRAMIDU IZ CELYH CHISEL $\{1, 2, \ldots, N\}$ RAVNO $$ N!/s_1s_2\ldots s_N= N!/\prod_{s\in M_N} s. \eqno(16) $$ nAPRIMER, CHISLO SPOSOBOV RASPOLOZHITX 26 BUKV $\{A, B, C, \ldots, Z\}$ NA RIS.~28 TAK, CHTOBY PO VERTIKALI SOHRANYALSYA ALFAVITNYJ PORYADOK, RAVNO $$ 26!/(26 \cdot 10 \cdot 6 \cdot 2 \cdot 1 \cdot 1^{12} \cdot 3^6 \cdot 7^2 \cdot 15^1). $$ tEPERX MY V SOSTOYANII PROANALIZIROVATX FAZU POSTROENIYA PIRAMIDY V ALGORITME~H, T. E. VYCHISLENIYA, KOTORYE ZAVERSHAYUTSYA DO TOGO, KAK V SHAGE H2 VPERVYE VYPOLNITSYA USLOVIE $l=1$. k SCHASTXYU, BLAGODARYA SLEDUYUSHCHEJ NIZHE TEOREME ANALIZ POSTROENIYA PIRAMIDY MOZHNO SVESTI K IZUCHENIYU NEZAVISIMYH OPERACIJ PROTASKIVANIYA. \proclaim tEOREMA H. eSLI ISHODNYMI DANNYMI DLYA ALGORITMA H SLUZHIT SLUCHAJNAYA PERESTANOVKA MNOZHESTVA $\{ 1, 2, \ldots, N\}$, TO V FAZE POSTROENIYA PIRAMIDY S ODINAKOVOJ VEROYATNOSTXYU MOZHET POLUCHITXSYA LYUBAYA IZ $N! /\left(\prod_{s\in M_N} s\right)$ VOZMOZHNYH PIRAMID. bOLEE moGO, VSE $\floor{N/2}$ OPERACIJ PROTASKIVANIYA, VYPOLNENNYE ZA VREMYA |TOJ FAZY, "RAVNOMERNY" V TOM SMYSLE, CHTO PO DOSTIZHENII SHAGA H8 VSE $s_l$ VOZMOZHNYH ZNACHENIJ PEREMENNOJ~$i$ RAVNOVEROYATNY. \proof pRIMENIM METOD, KOTORYJ V CHISLENNOM ANALIZE NAZYVAETSYA METODOM "OBRATNOJ ZADACHI". pUSTX V KACHESTVE ODNOGO IZ VOZMOZHNYH REZULXTATOV OPERACII PROTASKIVANIYA ZADANA PIRAMIDA $K_1$ \dots{} $K_N$ S KORNEM V UZLE~$l$; TOGDA YASNO, CHTO IMEETSYA VSEGO~$s_l$ ISHODNYH KONFIGURACIJ $K'_1$ \dots{} $K'_N$ FAJLA, KOTORYE POSLE PROTASKIVANIYA DAYUT TAKOJ REZULXTAT. vSE |TI ISHODNYE KONFIGURACII IMEYUT RAZLICHNYE ZNACHENIYA $K'_l$, SLEDOVATELXNO, RASSUZHDAYA V OBRATNOM NAPRAVLENII, SUSHCHESTVUET ROVNO $s_l$ $s_{l+1}$ \dots{} $s_N$ ISHODNYH PERESTANOVOK MNOZHESTVA $\{1, 2, \ldots, N\}$, KOTORYE POSLE ZAVERSHENIYA OPERACII PROTASKIVANIYA V POZICIYU~$l$ DAYUT KONFIGURACIYU $K_1$ \dots{} $K_N$. sLUCHAJ $l=1$ TIPICHEN: PUSTX $K_1$ \dots{} $K_N$---PIRAMIDA, I PUSTX $K'_1$ \dots{} $K'_N$---FAJL, KOTORYJ PREOBRAZUETSYA V $K_1$ \dots{} $K_N$ V REZULXTATE PROTASKIVANIYA PRI $l=1$, $K=K'_1$. eSLI $K=K_i$, TO DOLZHNY IMETX MESTO RAVENSTVA $K'_i=K_{\floor{i/2}}$, $K'_{\floor{i/2}}=K_{\floor{i/4}}$ I T. D., PRI |TOM $K'_j=K_j$ DLYA VSEH $j$, NE LEZHASHCHIH NA PUTI OT~$1$ K~$i$. oBRATNO, PRI LYUBOM~$i$ V REZULXTATE TAKOGO POSTROENIYA POLUCHAETSYA FAJL $K'_1$ \dots{} $K'_N$, TAKOJ, CHTO (a) OPERACIYA PROTASKIVANIYA PREOBRAZUET %% 189 FAJL $K'_1$ \dots{} $K'_N$ V $K_1$ \dots{} $K_N$ I (b) $K_{\floor{j/2}}\ge K_j$ PRI $2 \le \floor{j/2}r$. pOKAZHITE, CHTO ESLI $K\ge K_{r+1}$, TO MOZHNO BYLO BY TAK UPROSTITX SHAG~H4, CHTOBY RAZVETVLENIE PROISHODILO LISHX PO DVUM PUTYAM. kAK NADO IZMENITX SHAG~H2, CHTOBY OBESPECHITX V PROCESSE PIRAMIDALXNOJ SORTIROVKI VYPOLNENIE USLOVIYA $K\ge K_{r+1}$? \ex[10] pOKAZHITE, CHTO PROSTAYA OCHEREDX---CHASTNYJ SLUCHAJ PRIORITETNOJ. (oB®YASNITE, KAKIE KLYUCHI NUZHNO PRISVAIVATX |LEMENTAM, CHTOBY PROCEDURA "NAIBOLXSHIJ IZ VKLYUCHENNYH---PERVYM ISKLYUCHAETSYA" BYLA |KVIVALENTNA PROCEDURE "PERVYM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA".) yaVLYAETSYA LI STEK TAKZHE CHASTNYM SLUCHAEM PRIORITETNOJ OCHEREDI? \rex[M22] (v.~e.~chARTRS.) pRIDUMAJTE BYSTRYJ ALGORITM POSTROENIYA TABLICY PROSTYH CHISEL $\le N$, V KOTOROM ISPOLXZUETSYA \emph{PRIORITETNAYA OCHEREDX} S CELXYU IZBEZHATX OPERACIJ DELENIYA. [\emph{uKAZANIE.} pUSTX NAIMENXSHIJ KLYUYA V PRIORITETNOJ OCHEREDI BUDET NAIMENXSHIM NECHETNYM NEPROSTYM CHISLOM, BOLXSHIM, CHEM SAMOE POSLEDNEE NECHETNOE CHISLO, VOSPRINYATOE KAK KANDIDAT V PROSTYE CHISLA. pOPYTAJTESX SVESTI K MINIMUMU CHISLO |LEMENTOV V |TOJ OCHEREDI.] \ex[20] pOSTROJTE |FFEKTIVNYJ ALGORITM, KOTORYJ VSTAVLYAET NOVYJ KLYUCH V DANNUYU PIRAMIDU IZ P |LEMENTOV, POROZHDAYA PIRAMIDU IZ $n+1$~|LEMENTOV. \ex[20] aLGORITM IZ UPR.~16 MOZHNO ISPOLXZOVATX DLYA POSTROENIYA PIRAMIDY VZAMEN METODA "UMENXSHENIYA $l$ DO~$1$", PRIMENYAEMOGO V ALGORITME~H. %%192 pOROZHDAYUT LI OBA METODA IZ ODNOGO I TOGO ZHE ISHODNOGO FAJLA ODNU I TU ZHE PIRAMIDU? \rex[21] (r.~u.~fLOJD) vO VREMYA FAZY VYBORA V ALGORITME PIRAMIDALXNOJ SORTIROVKI KLYUCH $K$, KAK PRAVILO, PRINIMAET DOVOLXNO MALYE ZNACHENIYA, I PO|TOMU POCHTI PRI VSEH SRAVNENIYAH V SHAGE H6 OBNARUZHIVAETSYA, CHTO $KK_j$, PEREJTI K SHAGU~\stp{8}. eSLI $i=j$, USTANOVITX $P_k\asg R_i$ I PEREJTI K SHAGU \stp{13}. \st[pERESYLKA $R_i$.] (shAGI \stp{4}--\stp{7} ANALOGICHNY SHAGAM M3--M4 ALGORITMA~M.) uSTANOVITX $R_k\asg R_i$, $k\asg k+d$. \st[sTUPENXKA VNIZ?] uVELICHITX $i$ NA~1. zATEM, ESLI $K_{i-1}\le K_i$, VOZVRATITXSYA K SHAGU \stp{3}. \st [pERESYLKA $R_j$.] uSTANOVITX $R_k\asg R_j$, $k\asg k+d$. \st[sTUPENXKA VNIZ?] uMENXSHITX $j$ NA~1. zATEM, ESLI $K_{j+1}\le K_j$, VOZVRATITXSYA K SHAGU \stp{6}; V PROTIVNOM SLUCHAE PEREJTI K SHAGU \stp{12}. %% 197 \st[pERESYLKA $R_j$.] (shAGI \stp{8}--\stp{11} DVOJSTVENNY PO OTNOSHENIYU K SHAGAM~\stp{4}--\stp{7}.) uSTANOVITX $R_k\asg R_j$, $k\asg k+d$. \st[sTUPENXKA VNIZ?] uMENXSHITX $j$ NA 1. zATEM, ESLI $K_{j+1}\le K_j$, VOZVRATITXSYA K SHAGU \stp{3}. \st[pERESYLKA $R_i$.] uSTANOVITX~$R_k\asg R_i$, $k\asg k+d$. \st[sTUPENXKA VNIZ?] uVELICHITX $i$ NA~$1$. zATEM, ESLI $K_{i-1}\le K_i$, VOZVRATITXSYA K SHAGU \stp{10}. \st[pEREKLYUCHENIE NAPRAVLENIYA.] uSTANOVITX $f\asg0$, $d\asg-d$ I VZAIMOZAMENITX $k\xchg l$. vOZVRATITXSYA K SHAGU \stp{3}. \st[pEREKLYUCHENIE OBLASTEJ.] eSLI $f=0$, TO USTANOVITX $s\asg 1-s$ I VOZVRATITXSYA K~\stp{2}. v PROTIVNOM SLUCHAE SORTIROVKA ZAVERSHENA; ESLI $s=0$, TO USTANOVITX $(R_1,~\ldots, R_N)\asg(R_{N+1}, \ldots, R_{2N})$. (eSLI REZULXTAT MOZHNO OSTAVITX V OBLASTI~$(R_{N+1}, \ldots, R_{2N})$, TO POSLEDNEE KOPIROVANIE NEOBYAZATELXNO.) \algend v |TOM ALGORITME ESTX ODNA NEBOLXSHAYA TONKOSTX, KOTORAYA OB®YASNYAETSYA V UPR.~5. zAPROGRAMMIROVATX ALGORITM~N DLYA MASHINY~\MIX\ NETRUDNO, NO OSNOVNYE SVEDENIYA O EGO POVEDENII MOZHNO POLUCHITX I BEZ POSTROENIYA VSEJ PROGRAMMY. eSLI FAJL SLUCHAEV, TO V NEM OKOLO ${1\over2}N$ VOZRASTAYUSHCHIH OTREZKOV, TAK KAK $K_i>K_{i+1}$ S VEROYATNOSTXYU~$1\over2$; PODROBNAYA INFORMACIYA O CHISLE OTREZKOV PRI NESKOLXKO OTLICHNYH PREDPOLOZHENIYAH BYLA POLUCHENA V P.~5.1.3. pRI KAZHDOM PROSMOTRE CHISLO OTREZKOV SOKRASHCHAETSYA VDVOE (ZA ISKLYUCHENIEM NEOBYCHNYH SLUCHAEV, TAKIH, KAK SITUACIYA, OPISANNAYA V UPR.~6). tAKIM OBRAZOM, CHISLO PROSMOTROV, KAK PRAVILO, SOSTAVLYAET OKOLO~$\log_2 N$. pRI KAZHDOM PROSMOTRE MY DOLZHNY PEREPISATX VSE $N$~ZAPISEJ, I, KAK POKAZANO V UPR.~2, B\'OLXSHAYA CHASTX VREMENI ZATRACHIVAETSYA V SHAGAH~N3, N4, N5, N8, N9. eSLI SCHITATX, CHTO RAVNYE KLYUCHI VSTRECHAYUTSYA S MALOJ VEROYATNOSTXYU, TO VREMYA, ZATRACHIVAEMOE VO VNUTRENNEM CIKLE, MOZHNO OHARAKTERIZOVATX SLEDUYUSHCHIM OBRAZOM: \ctable{ \hfill# & # & #\cr \hbox{shAG}\hfill&\hfill\hbox{oPERACII}\hfill&\hfill\hbox{vREMYA}\hfill\cr $\matrix{N3\cr}$ & $\matrix{|CMPA|, |JG|, |JE|\cr}$ & $\matrix{3.5u}$ \cr $\hbox{lIBO}\left\{ \matrix{ N4\cr N5\cr }\right.$ & $ \matrix{ |STA|, |INC| \hfill\cr |INC|, |LDA|, |CMPA|, |JGE|\hfill \cr } $ & $\matrix{ \phantom{0.}3u\cr \phantom{0.}6u\cr }$ \cr $\hbox{lIBO}\left\{ \matrix{ N8 \cr N9 \cr }\right.$ & $\matrix{ |STX|, |INC|\hfill \cr |DEC|, |LDX|, |CMPX|, |JGE|\hfill\cr }$ & $\matrix{ \phantom{0.}3u\cr \phantom{0.}6u\cr }$ \cr } tAKIM OBRAZOM, PRI KAZHDOM PROSMOTRE NA KAZHDUYU ZAPISX ZATRACHIVAETSYA $12.5$~EDINIC VREMENI, I OBSHCHEE VREMYA RABOTY ASIMPTOTICHESKI PRIBLIZHAETSYA K~$12.5N\log_2 N$ KAK V SREDNEM, TAK I V NAIHUDSHEM SLUCHAE. eTO MEDLENNEE BYSTROJ SORTIROVKI I NE NASTOLXKO LUCHSHE VREMENI RABOTY PIRAMIDALXNOJ SORTIROVKI, CHTOBY OPRAVDATX VDVOE BOLXSHIJ RASHOD PAMYATI, TAK KAK ASIMPTOTICHESKOE VREMYA RABOTY PROGRAMMY~5.2.3H RAVNO $16N\log_2 N$. %% 198 v ALGORITME~N GRANICY MEZHDU OTREZKAMI POLNOSTXYU OPREDELYAYUTSYA "STUPENXKAMI VNIZ". tAKOJ PODHOD OBLADAET TEM VOZMOZHNYM PREIMUSHCHESTVOM, CHTO ISHODNYE FAJLY S PREOBLADANIEM VOZRASTAYUSHCHEGO \emph{ILI UBYVAYUSHCHEGO} RASPOLOZHENIYA |LEMENTOV MOGUT OBRABATYVATXSYA OCHENX BYSTRO, NO PRI |TOM ZAMEDLYAETSYA OSNOVNOJ CIKL VYCHISLENIJ. vMESTO PROVEROK STUPENEK VNIZ MOZHNO PRINUDITELXNO USTANOVITX DLINU OTREZKOV, SCHITAYA, CHTO VSE OTREZKI ISHODNOGO FAJLA IMEYUT DLINU~$1$, POSLE PERVOGO PROSMOTRA VSE OTREZKI (KROME, VOZMOZHNO, POSLEDNEGO) IMEYUT DLINU 2, \dots, POSLE $k\hbox{-Go}$ PROSMOTRA VSE OTREZKI (KROME, VOZMOZHNO, POSLEDNEGO) IMEYUT DLINU~$2^k$. v OTLICHIE OT "ESTESTVENNOGO" SLIYANIYA V ALGORITME~N TAKOJ SPOSOB NAZYVAETSYA \emph{PROSTYM} DVUHPUTEVYM SLIYANIEM. aLGORITM PROSTOGO DVUHPUTEVOGO SLIYANIYA OCHENX NAPOMINAET ALGORITM~N---ON OPISYVAETSYA, PO SUSHCHESTVU, TOJ ZHE BLOK-SHEMOJ; TEM NE MENEE METODY DOSTATOCHNO OTLICHAYUTSYA DRUG OT DRUGA, I PO|TOMU STOIT ZAPISATX VESX ALGORITM CELIKOM. \alg S.(sORTIROVKA PROSTYM DVUHPUTEVYM SLIYANIEM.) kAK I V ALGORITME~N, PRI SORTIROVKE ZAPISEJ $R_1$, \dots, $R_N$ ISPOLXZUYUTSYA DVE OBLASTI PAMYATI. \st[nACHALXNAYA USTANOVKA.] uSTANOVITX $s\asg0$, $p\asg1$. (sMYSL PEREMENNYH~$s$, $i$, $j$, $k$, $l$, $d$ SM. V ALGORITME~N. zDESX $p$---RAZMER VOZRASTAYUSHCHIH OTREZKOV, KOTORYE BUDUT SLIVATXSYA VO VREMYA TEKUSHCHEGO PROSMOTRA; $q$ I~$r$---KOLICHESTVA NESLITYH |LEMENTOV V OTREZKAH.) \st[pODGOTOVKA K PROSMOTRU.] eSLI $s=0$, TO USTANOVITX $i\asg1$, $j\asg N$, $k\asg N$, $l\asg2N+1$; ESLI $s=1$, TO USTANOVITX $i\asg N+1$, $j\asg2N$, $k\asg0$, $l\asg N+1$. zATEM USTANOVITX $d\asg1$, $q\asg p$, $r\asg p$. \st[sRAVNENIE $K_i:K_j$.] eSLI $K_i>K_j$, TO PEREJTI K SHAGU~\stp{8}. \st[pERESYLKA $R_i$] uSTANOVITX $k\asg k+d$, $R_k\asg R_i$. \st[kONEC OTREZKA?] uSTANOVITX $i\asg i+1$, $q\asg q-1$. eSLI $q > 0$, TO VOZVRATITXSYA K SHAGU~\stp{3}. \st[pERESYLKA $R_j$.] uSTANOVITX $k\asg k+d$. zATEM, ESLI $k=l$, PEREJTI K SHAGU~\stp{13}; V PROTIVNOM SLUCHAE USTANOVITX $R_k\asg R_j$. \st[kONEC OTREZKA?] uSTANOVITX $j\asg j-1$, $r\asg r-1$. eSLI~$r>0$, VOZVRATITXSYA K SHAGU \stp{6}; V PROTIVNOM SLUCHAE PEREJTI K SHAGU \stp{12}. \st [pERESYLKA $R_j$.] uSTANOVITX $k\asg k+d$, $R_k\asg R_j$ \st[kONEC OTREZKA?] uSTANOVITX $j\asg j-1$, $r\asg r-1$. eSLI~$r> 0$, TO VOZVRATITXSYA K SHAGU~\stp{3}. \st[pERESYLKA $R_i$.] uSTANOVITX $k\asg k+d$. zATEM, ESLI $k=l$, PEREJTI K SHAGU~\stp{13}; V PROTIVNOM SLUCHAE USTANOVITX $R_k\asg R_i$. %% 199 \st[kONEC OTREZKA?] uSTANOVITX $i\asg i+1$, $q\asg q-1$. eSLI $q > 0$, TO VOZVRATITXSYA K SHAGU \stp{10}. \st[pEREKLYUCHENIE NAPRAVLENIYA.] uSTANOVITX $q\asg p$, $r\asg p$, $d\asg -d$ I VZAIMOZAMENITX $k\xchg l$. vOZVRATITXSYA K SHAGU \stp{3}. \st[pEREKLYUCHENIE OBLASTEJ.] uSTANOVITX $p\asg p+p$. eSLI $pK_q$, TO PEREJTI K~\stp{6}. \st[pRODVINUTX $p$.] uSTANOVITX $\abs{L_s}\asg p$, $s\asg p$, $p\asg L_p$. eSLI $p>0$, TO VOZVRATITXSYA K~\stp{3}. \st[zAKONCHITX PODSPISOK.] uSTANOVITX $L_s\asg q$, $s\asg t$. zATEM USTANOVITX $t\asg q$ I~$q\asg L_q$ ODIN ILI BOLEE RAZ, POKA NE STANET $q\le 0$, POSLE CHEGO PEREJTI K~\stp{8}. \st[pRODVINUTX $q$.] (shAGI \stp{6} I~\stp{7} DVOJSTVENNY PO OTNOSHENIYU K~\stp{4} I~\stp{5}.) uSTANOVITX $\abs{L_s}\asg q$, $s\asg q$, $q\asg L_q$. eSLI~$q>0$, TO VOZVRATITXSYA K~\stp{3}. \st[zAKONCHITX PODSPISOK.] uSTANOVITX $L_s\asg p$, $s\asg t$. zATEM USTANOVITX $t\asg p$ I~$p\asg L_p$ ODIN ILI BOLEE RAZ, POKA NE STANET~$p>0$. \st[kONEC PROSMOTRA?] (k |TOMU MOMENTU $p\le 0$ I~$q\le 0$, TAK KAK OBA UKAZATELYA PRODVINULISX DO KONCA SOOTVETSTVUYUSHCHIH PODSPISKOV.) uSTANOVITX~$p\asg -p$, $q\asg -q$. eSLI $q=0$, TO USTANOVITX~$\abs{L_s}\asg p$, $\abs{L_t}\asg 0$, I VOZVRATITXSYA K~\stp{2}; V PROTIVNOM SLUCHAE VOZVRATITXSYA K~\stp{3}. \algend pRIMER RABOTY |TOGO ALGORITMA PRIVEDEN V TABL.~3, V KOTOROJ POKAZANY SVYAZI K MOMENTU VYPOLNENIYA SHAGA~L2. pO OKONCHANII RABOTY ALGORITMA MOZHNO, POLXZUYASX METODOM IZ UPR.~5.2--12, PERERAZMESTITX ZAPISI TAK, CHTOBY IH KLYUCHI BYLI UPORYADOCHENY. mOZHNO ZAMETITX INTERESNUYU ANALOGIYU MEZHDU SLIYANIEM SPISKOV I SLOZHENIEM RAZREZHENNYH MNOGOCHLENOV (SM. ALGORITM 2.2.4a). {\catcode`\!=\active\def!#1.{\omit\hfill$#1$\hfill} \htable{tABLICA 3}% {sORTIROVKA POSREDSTVOM SLIYANIYA SPISKOV}% {\bskip$#$\bskip&&\hfill$#$\bskip\cr j &!0.& !1.& !2.& !3.& !4.& !5.& !6.& !7.& !8.& !9.&!10.&!11.&!12.&!13.&!14.&!15.&!16.&!17.\cr K_i & - & 503& 087& 512& 061& 908& 170& 897& 275& 653& 426& 154& 509& 612& 677& 765& 703& -\cr L_j & 1 & -3& -4& -5& -6& -7& -8& -9& -10& -11& -12& -13& -14& -15& -16& 0& 0& 2\cr L_j & 2 & -6& 1& -8& 3& -10& 5& -11& 7& -13& 9& 12& -16& 14& 0& 0& 15& 4\cr L_j & 4 & 3& 1& -11& 2& -13& 8& 5& 7& 0& 12& 10& 9& 14& 16& 0& 15& 6\cr L_j & 4 & 3& 6& 7& 2& 0& 8& 5& 1& 14& 12& 10& 13& 9& 16& 0& 15& 11\cr L_j & 4 & 12& 11& 13& 2& 0& 8& 5& 10& 14& 1& 6& 3& 9& 16& 7& 15& 0\cr } } nAPISHEM TEPERX \MIX-PROGRAMMU DLYA ALGORITMA~L, CHTOBY VYYASNITX, STOLX LI VYGODNO OPERIROVATX SPISKAMI S TOCHKI ZRENIYA VREMENI, KAK I S TOCHKI ZRENIYA PROSTRANSTVA? %%202 \prog L.(sORTIROVKA POSREDSTVOM SLIYANIYA SPISKOV.) dLYA UDOBSTVA PREDPOLAGAETSYA, CHTO ZAPISI ZANIMAYUT ODNO SLOVO, PRICHEM $L_j$ HRANITSYA V POLE $(0:2)$, A $K_j$---V POLE $(3:5)$ YACHEJKI $|INPUT|+j$; ZNACHENIYA REGISTROV: $|rI1|\equiv p$, $|rI2|\equiv q$, $|rI3|\equiv s$, $|rI4|\equiv t$ $|rA|\equiv R_q$; $N\ge 2$. \code L & EQU & 0:2 & & oPREDELENIE IMEN POLEJ. ABSL & EQU & 1:2 KEY & EQU & 3:5 START& ENT1 & N-2 & 1 & L1. pODGOTOVITX DVA SPISKA. & ENNA & 2,1 & N-2 & STA & INPUT,1(L) & N-2 & $L_i\asg -(i+2)$. & DEC1 & 1 & N-2 & J1P & *-3 & N-2 & $N-2\ge i>0$. & ENTA & 1 & 1 & STA & INPUT(L) & 1 & $L_0\asg 1$. & ENTA & 2 & 1 & STA & INPUT+N+1(L) & 1 & $L_{N+1}\asg2$. & STZ & INPUT+ N-1(L)& 1 & $L_{N-1}\asg 0$. & STZ & INPUT +N(L) & 1 & $L_N\asg 0$. & JMP & L2 & 1 & k L2. L3Q & LDA & INPUT,2 & C''+B'& L3. sRAVNITX $K_p:K_q$. L3P & CMPA & INPUT,1(KEY) & C & JL & L6 & C & k L6, ESLI $K_q0$. L5 & ST2 & INPUT,3(L) & B' & L5. zAKONCHITX PODSPISOK. $L_s\asg q$. & ENT3 & 0,4 & B' & $s\asg t$. & ENT4 & 0,2 & D' & $t\asg q$. & LD2 & INPUT,2(L) & D' & $q\asg L_q$. & J2P & *-2 & D' & pOVTORITX, ESLI $q>0$. & JMP & L8 & B' & k L8 L6 & ST2 & INPUT,3(ABSL)& C'' & L6. pRODVINUTX~$q$. $\abs{L_s}\asg q$. & ENT3 & 0,2 & C'' & $s\asg q$. & LD2 & INPUT,2(L) & C'' & $q\asg L_q$. & J2P & L3Q & C'' & k L3, ESLI~$q>0$. L7 & ST1 & INPUT,3(L) & B'' & L7. zAKONCHITX PODSPISOK. $L_s\asg p$. & ENT3 & 0,4 & B'' & $s\asg t$. & ENT4 & 0,1 & D'' & $t\asg p$. & LD1 & INPUT, 1(L) & D'' & $p\asg L_p$. & J1P & *-2 & D'' & pOVTORITX, ESLI~$p>0$. L8 & ENN1 & 0,1 & B & L8. kONEC PROSMOTRA? $p\asg -p$. & ENN2 & 0,2 & B & $q\asg -q$. & J2NZ & L3Q & B & k L3, ESLI $q\ne0$. & ST1 & INPUT,3(ABSL)& A & $\abs{L_s}\asg p$. & STZ & INPUT,4(ABSL)& A & $\abs{L_t}\asg0$. %%203 L2 & ENT3 & 0 & A+1 & L2. nACHATX NOVYJ PROSMOTR, $s\asg0$. & ENT4 & N+1 & A+1 & $t\asg N+1$. & LD1 & INPUT (L) & A+1 & $p\asg L_s$. & LD2 & INPUT+N+1(L) & A+1 & $q\asg L_t$. & J2NZ & L3Q & A+1 & k L3, ESLI $q \ne 0$. \endcode vREMYA RABOTY |TOJ PROGRAMMY MOZHNO OCENITX PRI POMOSHCHI METODOV, KOTORYMI MY UZHE NE RAZ POLXZOVALISX (SM. UPR.~13, 14); V SREDNEM ONO RAVNO PRIBLIZITELXNO $(10N \log_2 N+4.92N)$~EDINIC S NEBOLXSHIM STANDARTNYM OTKLONENIEM PORYADKA $\sqrt{N}$. v UPR.~15 POKAZANO, CHTO ZA SCHET NEKOTOROGO UDLINENIYA PROGRAMMY MOZHNO SOKRATITX VREMYA PRIMERNO DO~$9N\log_2N$. iTAK, V SLUCHAE VNUTRENNEGO SLIYANIYA SVYAZANNOE RASPREDELENIE PAMYATI IMEET BESSPORNYE PREIMUSHCHESTVA PERED POSLEDOVATELXNYM RASPREDELENIEM: TREBUETSYA MENXSHE PAMYATI, I PROGRAMMA RABOTAET NA 10--20\% BYSTREE. aNALOGICHNYE ALGORITMY OPUBLIKOVANY l.~dZH.~vUDRAMOM [{\sl IBM Systems J.\/}, {\bf 8} (1969), 189--203] I a.~d.~vUDALLOM [{\sl sOTR. J.\/}, {\bf 13} (1970), 110--111]. \excercises \ex[20] oBOBSHCHITE ALGORITM~M NA \emph{$k\hbox{-PUTEVOE}$ SLIYANIE} ISHODNYH FAJLOV $x_{i1}\le \ldots\le x_{im_i}$ PRI $i=1,$ 2, \dots, $k$. \ex[m24] sCHITAYA, CHTO VSE $\perm{m+n}{m}$ VOZMOZHNYH RASPOLOZHENIJ $m$~|LEMENTOV~$x$ SREDI $n$~|LEMENTOV~$y$ RAVNOVEROYATNY, NAJDITE MATEMATICHESKOE OZHIDANIE I STANDARTNOE OTKLONENIE CHISLA VYPOLNENII SHAGA~M2 V ALGORITME~M. chEMU RAVNY MAKSIMALXNOE I MINIMALXNOE ZNACHENIYA |TOJ VELICHINY? \rex[20] \exhead(iZMENENIE.) dANY ZAPISI $R_1$,~\dots, $R_M$ I~$R'_1$, ~\dots, $R'_N$, KLYUCHI KOTORYH RAZLICHNY I UPORYADOCHENY, T.~E.~$K_1<\ldotsK_3, K_4>K_5, K_6>K_7, K_8>K_9,\cr K_{10}e_2>\ldots>e_t\ge0$, $t\ge1$. dOKAZHITE, CHTO MAKSIMALXNOE CHISLO SRAVNENIJ KLYUCHEJ, VYPOLNYAEMYH ALGORITMOM~L, RAVNO $1-2^{e_t}+\sum{1\le k\le t}(e_k+k-1)2^{e_k}$. \ex[20] eSLI PROMODELIROVATX VRUCHNUYU RABOTU ALGORITMA~L, TO OBNARUZHITSYA, CHTO V NEM INOGDA VYPOLNYAYUTSYA LISHNIE OPERACII; PRIMERNO V POLOVINE SLUCHAEV NE NUZHNY PRISVAIVANIYA $\abs{L_s}\asg p$, $\abs{L_s}\asg q$ V SHAGAH~L4 I~L6, POSKOLXKU MY IMEEM $L_s=p$ (ILI~$q$) VSYAKIJ RAZ, KOGDA VOZVRASHCHAEMSYA IZ SHAGA~L4 (ILI L6) K~L3. kAK ULUCHSHITX PROGRAMMU~L, IZBAVIVSHISX OT |TIH LISHNIH PRISVAIVANII? \ex[28] rAZRABOTAJTE ALGORITM SLIYANIYA SPISKOV, PODOBNYJ ALGORITMU~L, NO OSNOVANNYJ NA TREHPUTEVOM SLIYANII. \ex[20] (dZH.~mAK-kARTI.) pUSTX DVOICHNOE PREDSTAVLENIE CHISLA~$N$ TAKOE ZHE, KAK V UPR.~14, I PREDPOLOZHIM, CHTO DANO $N$~ZAPISEJ, ORGANIZOVANNYH V $t$ UPORYADOCHENNYH PODFAJLOV, IMEYUSHCHIH RAZMERY SOOTVETSTVENNO $2^{e_1}$, $2^{e_2}$, \dots, $2^{e_t}$. pOKAZHITE, KAK MOZHNO SOHRANITX TAKOE SOSTOYANIE PRI DOBAVLENII $(N+1)\hbox{-J}$ ZAPISI I~$N\asg N+1$. (pOLUCHENNYJ ALGORITM MOZHNO NAZVATX "OPERATIVNOJ" SORTIROVKOJ SLIYANIEM.) \ex[40] (m.~a.~kRONROD.) mOZHNO LI OTSORTIROVATX FAJL IZ $N$~ZAPISEJ, SODERZHASHCHIJ VSEGO DVA OTREZKA: $$ K_1\le\ldots\le K_M\quad\hbox{I}\quad K_{M+1}\le\ldots\le K_N, $$ zA $O(N)$ OPERACIJ V PAMYATI S PROIZVOLXNYM DOSTUPOM, \emph{ISPOLXZUYA LISHX NEBOLXSHOE DOPOLNITELXNOE PROSTRANSTVO PAMYATI FIKSIROVANNOGO RAZMERA}, NE ZAVISYASHCHEGO OT~$M$ I~$N$? (vSE ALGORITMY SLIYANIYA, OPISANNYE V |TOM PUNKTE, ISPOLXZUYUT DOPOLNITELXNOE PROSTRANSTVO PAMYATI, PROPORCIONALXNOE~$N$.) \ex[26] rASSMOTRIM ZHELEZNODOROZHNYJ RAZ®EZD S $n$~"STEKAMI", KAK POKAZANO NA RIS.~31 PRI $n=5$; TAKOJ RAZ®EZD IMEET NEKOTOROE OTNOSHENIE K ALGORITMAM SORTIROVKI S $n$~PROSMOTRAMI. v UPR.~S~2.2.1--2 PO~2.2.1--5 MY RASSMOTRELI RAZ®EZDY S ODNIM STEKOM. vY VIDELI, CHTO ESLI S PRAVOGO KONCA POSTUPAET $N$~VAGONOV, TO SLEVA MOZHET POYAVITXSYA SRAVNITELXNO NEBOLXSHOE KOLICHESTVO IZ $N$~VSEVOZMOZHNYH PERESTANOVOK |TIH VAGONOV. %% 205 pREDPOLOZHIM, CHTO V RAZ®EZD S $n$~STEKAMI SPRAVA POSTUPAET $2^n$~VAGONOV. dOKAZHITE, CHTO PRI POMOSHCHI PODHODYASHCHEJ POSLEDOVATELXNOSTI OPERACIJ SLEVA \emph{MOZHNO POLUCHITX} LYUBUYU IZ~$2^n!$ VSEVOZMOZHNYH PERESTANOVOK |TIH VAGONOV. (kAZHDYJ STEK DOSTATOCHNO VELIK, I PRI NEOBHODIMOSTI V NEGO MOZHNO POMESTITX VSE VAGONY). \ex[47] v OBOZNACHENIYAH UPR.~2.2.1--4 PRI POMOSHCHI RAZ®EZDOV S $n$~STEKAMI MOZHNO POLUCHITX NE BOLEE $a^n_N$~PERESTANOVOK $N$~|LEMENTOV; SLEDOVATELXNO, DLYA \picture{rIS. 31.zhELEZNODOROZHNYJ RAZ®EZD S PYATXYU "STEKAMI".} POLUCHENIYA VSEH $N!$~PERESTANOVOK TREBUETSYA NE MENEE $\log N!/\log a_N\approx \log_4 N$~STEKOV. v UPR.~19 POKAZANO, CHTO NUZHNO NE BOLEE $\ceil{\log_2 N}$~STEKOV. kAKOVA ISTINNAYA SKOROSTX ROSTA NEOBHODIMOGO CHISLA STEKOV PRI $N\to\infty$? \ex[23] (e.~dZH.~sMIT.) oB®YASNITE, KAK MOZHNO OBOBSHCHITX ALGORITM~L, CHTOBY ON, POMIMO SORTIROVKI, VYCHISLYAL TAKZHE CHISLO \emph{INVERSIJ} V ISHODNOJ PERESTANOVKE. \subsubchap{rASPREDELYAYUSHCHAYA SORTIROVKA} % 5.2.5 mY PODHODIM TEPERX K INTERESNOMU KLASSU METODOV SORTIROVKI, KOTORYJ, KAK POKAZANO V P.~5.4.7, PO SUSHCHESTVU, PRYAMO \emph{PROTIVOPOLOZHEN} SLIYANIYU. chITATELYAM, ZNAKOMYM S PERFOKARTOCHNYM OBORUDOVANIEM, HOROSHO IZVESTNA |FFEKTIVNAYA PROCEDURA, PRIMENYAEMAYA V MASHINAH DLYA SORTIROVKI KART I OSNOVANNAYA NA SRAVNENII CIFR KLYUCHEJ; TU ZHE IDEYU MOZHNO PRISPOSOBITX I DLYA PROGRAMMIROVANIYA. oNA OBSHCHEIZVESTNA POD NAZVANIYAMI "PORAZRYADNAYA SORTIROVKA", "CIFROVAYA SORTIROVKA" ILI "KARMANNAYA SORTIROVKA". pREDPOLOZHIM, NAM NUZHNO OTSORTIROVATX KOLODU IZ 52~IGRALXNYH KART. oPREDELIM UPORYADOCHENIE PO STARSHINSTVU (DOSTOINSTVU) KART V MASTI $$ t<2<3<4<5<6<7<8<9<10j$, NO $a_j1$ (NE PERVYJ PROSMOTR), TO USTANOVITX~$|P|\asg|LINK|(|P|)$ I VOZVRATITXSYA K~\stp{3}, ESLI~$|P|\ne\NULL$. \st[vYPOLNITX ALGORITM~H.] (tEPERX MY UZHE RASPREDELILI VSE |LEMENTY PO STOPKAM.) vYPOLNITX PRIVEDENNYJ NIZHE ALGORITM~H, KOTORYJ SCEPLYAET OTDELXNYE "STOPKI" V ODIN SPISOK, PODGOTAVLIVAYA IH K SLEDUYUSHCHEMU PROSMOTRU. zATEM USTANOVITX~$|P|\asg|BOTM|[0]$, UKAZATELX NA PERVYJ |LEMENT OB®EDINENNOGO SPISKA. (sM. UPR.~3.) \algend \alg H.(sCEPLENIE OCHEREDEJ.) iZ $M$~DANNYH OCHEREDEJ SO SVYAZYAMI, UDOVLETVORYAYUSHCHIMI SOGLASHENIYAM ALGORITMA~R, DANNYJ ALGORITM SOZDAET ODNU OCHEREDX, MENYAYA PRI |TOM NE BOLEE $M$~SVYAZEJ. v REZULXTATE $|BOTM|[0]$ UKAZYVAET NA PERVYJ |LEMENT, I STOPKA~0 PREDSHESTVUET STOPKE~1, \dots, PREDSHESTVUET STOPKE~$(M-1)$. \st[nACHALXNAYA USTANOVKA.] uSTANOVITX $i\asg 0$. \st[uKAZATELX NA VERSHINU STOPKI.] uSTANOVITX $|P|\asg|TOP|[i]$. \st[sLEDUYUSHCHAYA STOPKA.] uVELICHITX~$i$ NA~1. eSLI $i=M$, TO USTANOVITX~$|LINK|(|P|)\asg\NULL$ I ZAVERSHITX RABOTU ALGORITMA. \st[sTOPKA PUSTA?] eSLI $|BOTM|[i]=\NULL$, To VOZVRATITXSYA K~\stp{z}. \st[sCEPITX STOPKI.] uSTANOVITX $|LINK| (|P|)\asg|BOTM|[i]$. vOZVRATITXSYA K~\stp{2}. \algend nA RIS.~33 POKAZANO SODERZHIMOE STOPOK POSLE KAZHDOGO IZ TREH PROSMOTROV, VYPOLNYAEMYH PRI SORTIROVKE NASHIH 16~CHISEL S~$M=10$. aLGORITM~R OCHENX PROSTO ZAPROGRAMMIROVATX DLYA MASHINY~\MIX, ESLI TOLXKO NAJTI UDOBNYJ, SPOSOB IZMENYATX OT PROSMOTRA K PROSMOTRU DEJSTVIYA V SHAGAH~R3 I~R5. v SLEDUYUSHCHEJ %%211 PROGRAMME |TOGO UDALOSX DOBITXSYA, NE ZHERTVUYA SKOROSTXYU VNUTRENNEGO CIKLA, PUTEM PREDVARITELXNOJ ZAPISI DVUH KOMAND V TELO PROGRAMMY. zAMETIM, CHTO $|TOP|[i]$ I~$|BOTM|[i]$ MOZHNO UPAKOVATX V ODNO SLOVO. \picture{rIS. 33. pORAZRYADNAYA SORTIROVKA S ISPOLXZOVANIEM SVYAZANNOGO RASPREDELENIYA PAMYATI (POKAZANO SODERZHIMOE VSEH DESYATI STOPOK POSLE KAZHDOGO PROSMOTRA). } \prog R.(pORAZRYADNAYA SORTIROVKA SPISKOV.) pREDPOLAGAETSYA, CHTO ISHODNYE KLYUCHI V YACHEJKAH OT~$|INPUT|+1$ DO~$|INPUT|+N$ SODERZHAT $p=3$~KOMPONENTY ($a_3$, $a_2$, $a_1$), HRANYASHCHIESYA SOOTVETSTVENNO V POLYAH $(1:1)$, $(2:2)$ I~$(3:3)$. (tAKIM OBRAZOM, SCHITAETSYA, CHTO ZNACHENIE~$M$ MENXSHE ILI RAVNO RAZMERU BAJTA MASHINY \MIX.) v POLE $(4:5)$ ZAPISI HRANITSYA SVYAZX~|LINK|. pUSTX $|TOP|[i]\equiv |PILES|+i(l :2)$ I~$|BOTM|[i]\equiv |PILES|+i(4:5)$ PRI $0\le ii\ge 0$. & LDA & R3SW,3 & 3 & STA & 3F & 3 & iZMENITX KOMANDY & LDA & R5SW,3 & 3 & DLYA $k$-GO PROSMOTRA. & STA & 5F & 3 3n & [LD2 & INPUT, 1(3:3)]& & R3. vYDELITX $k$-YU CIFRU KLYUCHA. 4H & LD4 & PILES,2 (TOP) & 3N & R4. sKORREKTIROVATX SVYAZI. & ST1 & INPUT,4(LINK) & 3N & $|LINK|(|TOP|[i])\asg|P|$. & ST1 & PILES,2(TOP) & 3N & $|TOP|[i]\asg|P|$. 5H & [DEC1& 1] & & R5. pEREJTI K SLEDUYUSHCHEJ ZAPISI. & J1NZ & 3B & 3N & k R3, ESLI PROSMOTR ZAKONCHEN. 6H & ENN2 & m & 3 & R6. vYPOLNITX ALGORITM n. & JMP & 7F & 3 & k n2 S $i\asg0$. R3SW & LD2 & INPUT, 1(1:1) & N & kOMANDA DLYA R3 PRI $k=3$. & LD2 & INPUT, 1(2:2) & N & kOMANDA DLYA R3 PRI $k=2$. & LD2 & INPUT, 1(3:3) & N & kOMANDA DLYA R3 PRI $k=1$. R5SW & LD1 & INPUT, 1(LINK)& N & kOMANDA DLYA R5 PRI $k=3$. & LD1 & INPUT, 1(LINK)& N & kOMANDA DLYA R5 PRI $k=2$. & DEC1 & 1 & N & kOMANDA DLYA R5 PRI $k=1$. 9H & LDA & PILES+M, 2(LINK)& 3M-3 & n4.sTOPKA PUSTA? & JAZ & 8F & 3M-3 & k nz, ESLI $|votm|[i]=\NULL$ %%213 & STA & INPUT, 1(LINK) & 3M-3-E & H5. sCEPITX STOPKI $|LINK|(|P|)\asg|BOTM|[i]$. 7H & LD1 & PILES+M, 2(TOP) & 3M-E & H2. uKAZATELX NA VERSHINU STOPKI. 8H & INC2 & 1 & 3M & H3. sLEDUYUSHCHAYA STOPKA, $i\asg i+1$. & J2NZ & 9B & 3M & k n4, ESLI $i\ne M$. & STZ & INPUT, 1(LINK) & 3 & $|LINK|(|P|)\asg\NULL$. & LD1 & PILES (LINK) & 3 & $|P|\asg|BOTM|[0]$. & DEC3 & 1 & 3 & J3NN & 2B & 3 & $1\le k\le 3$ \endcode vREMYA RABOTY PROGRAMMY~R RAVNO $32N+48M+38-4E$, GDE $N$---CHISLO ISHODNYH ZAPISEJ, $M$---OSNOVANIE SISTEMY SCHISLENIYA (CHISLO STOPOK), A $E$---CHISLO VSTRETIVSHIHSYA PUSTYH STOPOK. sRAVNENIE S DRUGIMI PROGRAMMAMI, POSTROENNYMI NA OSNOVE ANALOGICHNYH PREDPOLOZHENIJ (PROGRAMMY~5.2.1m, 5.2.4L), GOVORIT YAVNO V POLXZU PROGRAMMY~R. vREMYA RABOTY $p\hbox{-PROHODNOGO}$ VARIANTA PROGRAMMY~R RAVNO $(11p-1)N+O(pM)$~EDINIC; KRITICHESKIJ FAKTOR, VLIYAYUSHCHIJ NA VREMYA RABOTY,---VNUTRENNIJ CIKL, KOTORYJ SODERZHIT PYATX OBRASHCHENIJ K PAMYATI I ODIN PEREHOD. dLYA TIPICHNOJ VYCHISLITELXNOJ MASHINY $M=b^r$ I~$p=\ceil{t/r}$, GDE $t$--- CHISLO CIFR V KLYUCHAH, PREDSTAVLENNYH V SISTEME SCHISLENIYA S OSNOVANIEM~$b$; S ROSTOM~$r$ UBYVAET~$p$, TAK CHTO MOZHNO VOSPOLXZOVATXSYA NASHIMI FORMULAMI DLYA OPREDELENIYA "NAILUCHSHEGO" ZNACHENIYA~$r$. eDINSTVENNAYA PEREMENNAYA VELICHINA V FORMULE VREMENI RABOTY---|TO $E$---CHISLO PUSTYH STOPOK, OBNARUZHENNYH V SHAGE n4. pREDPOLOZHIM, CHTO VSE $M^N$~POSLEDOVATELXNOSTEJ CIFR $M\hbox{-ICHNOJ}$ SISTEMY SCHISLENIYA RAVNOVEROYATNY. iZ IZUCHENIYA "POKER-TESTA" V P.~3.3.2D MY UMEEM VYCHISLYATX VEROYATNOSTX TOGO, CHTO V KAZHDOM PROSMOTRE VSTRETITSYA ROVNO $M-r$ PUSTYH STOPOK; ONA RAVNA $$ {M(M-1)\ldots(M-r+1)\over M^N}\left\{{N\atop r}\right\}, $$ GDE $\left\{{N\atop r}\right\}$---CHISLO sTIRLINGA VTOROGO RODA. sOGLASNO UPR. 5, $$ E=\bigl(\min\max (M-N, 0)p, \ave M(1-{1\over M})^Np,\max(M-1)p\bigr). $$ v POSLEDNIE GODY POYAVLYAETSYA VSE BOLXSHE "TRUBOPROVODNYH", ILI "MAGISTRALXNYH", VYCHISLITELXNYH MASHIN. eTI MASHINY IMEYUT NESKOLXKO ARIFMETICHESKIH USTROJSTV I SHEMU "OPEREZHENIYA", TAK CHTO OBRASHCHENIYA K PAMYATI I VYCHISLENIYA MOGUT V ZNACHITELXNOJ STEPENI SOVMESHCHATXSYA VO VREMENI; NO |FFEKTIVNOSTX %%214 TAKIH MASHIN ZAMETNO PONIZHAETSYA PRI NALICHII USLOVNYH PEREHODOV, ESLI TOLXKO |TI PEREHODY NE PROISHODYAT POCHTI VSEGDA V ODNOM I TOM ZHE NAPRAVLENII. vNUTRENNIJ CIKL PORAZRYADNOJ SORTIROVKI HOROSHO PRISPOSOBLEN DLYA TAKIH MASHIN, POSKOLXKU |TO PROSTOE ITERATIVNOE VYCHISLENIE, TIPICHNOE "PEREZHEVYVANIE CHISEL". pO|TOMU \emph{DLYA MAGISTRALXNYH MASHIN PORAZRYADNAYA SORTIROVKA OBYCHNO BYVAET NAIBOLEE |FFEKTIVNYM METODOM IZ VSEH IZVESTNYH METODOV VNUTRENNEJ SORTIROVKI}, PRI USLOVII CHTO $N$ NE SLISHKOM MALO I KLYUCHI NE SLISHKOM DLINNYE. rAZUMEETSYA, ESLI KLYUCHI UZH OCHENX DLINNYE, PORAZRYADNAYA SORTIROVKA NE TAK |FFEKTIVNA. pREDSTAVXTE SEBE, NAPRIMER, CHTO NUZHNO OTSORTIROVATX PERFOKARTY PO KLYUCHU IZ 80~KOLONOK; KAK PRAVILO, VSTRETITSYA OCHENX MALO PAR KART, U KOTORYH BY SOVPALI PERVYE PYATX KOLONOK, TAK CHTO PERVYE 75~PROSMOTROV VYPOLNYATSYA POCHTI VPUSTUYU. pRI ANALIZE OBMENNOJ PORAZRYADNOJ SORTIROVKI MY OBNARUZHILI, CHTO VOVSE NE OBYAZATELXNO PROVERYATX MNOGO BITOV KLYUCHEJ, ESLI PROSMATRIVATX IH NE SPRAVA NALEVO, A SLEVA NAPRAVO. pO|TOMU DAVAJTE VOZVRATIMSYA K IDEE PORAZRYADNOJ SORTIROVKI, V KOTOROJ KLYUCHI PROSMATRIVAYUTSYA, NACHINAYA SO STARSHIH CIFR (sc), A NE S MLADSHIH CIFR (mc). mY UZHE OTMECHALI, CHTO sc-PORAZRYADNAYA SORTIROVKA ESTESTVENNYM OBRAZOM PRIHODIT NA UM. v SAMOM DELE, NETRUDNO PONYATX, POCHEMU PRI SORTIROVKE POCHTY V OTDELENIYAH SVYAZI POLXZUYUTSYA IMENNO |TIM METODOM. bOLXSHOE KOLICHESTVO PISEM MOZHNO OTSORTIROVATX PO OTDELXNYM MESHKAM, SOOTVETSTVUYUSHCHIM GEOGRAFICHESKIM OBLASTYAM; TEPERX KAZHDYJ MESHOK SODERZHIT UZHE MENXSHEE KOLICHESTVO PISEM, KOTORYE MOZHNO NEZAVISIMO SORTIROVATX PO DRUGIM MESHKAM, SOOTVETSTVUYUSHCHIM VSE MENXSHIM I MENXSHIM GEOGRAFICHESKIM RAJONAM. (rAZUMEETSYA, PREZHDE CHEM PODVERGATX PISXMA DALXNEJSHEJ SORTIROVKE, IH MOZHNO PEREPRAVITX POBLIZHE K MESTU NAZNACHENIYA.) eTOT PRINCIP "RAZDELYAJ I VLASTVUJ" VESXMA PRIVLEKATELEN, I EDINSTVENNAYA PRICHINA EGO NEPRIGODNOSTI DLYA SORTIROVKI PERFOKART V TOM, CHTO BOLXSHOE KOLICHESTVO STOPOK PRIVODIT K PUTANICE. eTIM ZHE YAVLENIEM OB®YASNYAETSYA OTNOSITELXNAYA |FFEKTIVNOSTX ALGORITMA~R (HOTYA ZDESX SNACHALA RASSMATRIVAYUTSYA mc), POTOMU CHTO NAM NIKOGDA NE PRIHODITSYA RABOTATX BOLEE CHEM S $M$~STOPKAMI I STOPKI PRIHODITSYA SCEPLYATX VSEGO $p$~RAZ. s DRUGOJ STORONY, NETRUDNO POSTROITX sc-PORAZRYADNYJ METOD S ISPOLXZOVANIEM SVYAZANNOGO RASPREDELENIYA PAMYATI S OTRICATELXNYMI SVYAZYAMI DLYA OBOZNACHENIE GRANIC MEZHDU STOPKAMI, KAK V ALGORITME 5.2.4L. (sM. UPR. 10.) pOZHALUJ, NAILUCHSHIJ KOMPROMISSNYJ VYHOD UKAZAL m.~d.~mAKLAREN [{\sl JACM\/}, {\bf 13} (1966), 404--411], KOTORYJ PREDLOZHIL ISPOLXZOVATX mc-SORTIROVKU, KAK V ALGORITME~R, \emph{NO LISHX V PRIMENENII K STARSHIM CIFRAM}. eTO NE BUDET POLNOJ SORTIROVKOJ FAJLA, NO V REZULXTATE FAJL STANOVITSYA POCHTI UPORYADOCHENNYM, T. E. %%215 V NEM OSTAETSYA OCHENX MALO INVERSIJ, TAK CHTO DLYA ZAVERSHENIYA SORTIROVKI MOZHNO VOSPOLXZOVATXSYA METODOM PROSTYH VSTAVOK. nASH ANALIZ ALGORITMA 5.2.1m PRIMENIM I K-|TOJ SITUACII; ESLI KLYUCHI RASPREDELENY RAVNOMERNO, TO POSLE SORTIROVKI FAJLA PO STARSHIM $p$~CIFRAM V NEM OSTANETSYA V SREDNEM $$ {1\over 4}N(N-1)M^{-p} $$ INVERSIJ. [sM. FORMULU~(5.2.1--14) I UPR.~5.2.1--38.] mAKLAREN VYCHISLIL SREDNEE CHISLO OBRASHCHENIJ K PAMYATI, PRIHODYASHCHEESYA NA ODIN OBRABATYVAEMYJ |LEMENT, I OKAZALOSX, CHTO OPTIMALXNYJ VYBOR ZNACHENIJ~$M$ I~$p$ (V PREDPOLOZHENII, CHTO $M$---STEPENX DVOJKI, KLYUCHI RAVNOMERNO RASPREDELENY I~$N/M^p\le 0.1$, TAK.CHTO OTKLONENIYA OT RAVNOMERNOGO RASPREDELENIYA PRIEMLEMY) OPISYVAETSYA SLEDUYUSHCHEJ TABLICEJ: \ctable{ \hfill$#$\bskip&&\bskip\hfill$#$\bskip\cr N= & 100 & 1000 & 5000 & 10000 & 50000 & 100000\cr \hbox{nAILUCHSHEE } M=& 32 & 128 & 256 & 512 & 1024 & 1024\cr \hbox{nAILUCHSHEE } p=& 2 & 2 & 2 & 2 & 2 & 2\cr \bar \beta(N)=& 19.3 & 18.5 & 18.2 & 18.2 & 18.1 & 18.0 \cr } zDESX $\bar\beta(N)$---SREDNEE CHISLO OBRASHCHENIJ K PAMYATI NA ODIN SORTIRUEMYJ |LEMENT; |TA VELICHINA OGRANICHENA PRI $N\to\infty$, ESLI VZYATX $p=2$ I~$M>\sqrt N$, TAK CHTO SREDNEE VREMYA SORTIROVKI ESTX $O(N)$, A NE $O(N \log N)$. eTOT METOD YAVLYAETSYA USOVERSHENSTVOVANIEM METODA VSTAVOK V NESKOLXKO SPISKOV (ALGORITM~5.2.1m), KOTORYJ, PO SUSHCHESTVU, PREDSTAVLYAET SOBOJ SLUCHAJ $p=1$. v UPR.~12 PRIVODITSYA INTERESNAYA PROCEDURA mAKLARENA DLYA OKONCHATELXNOGO PERERAZMESHCHENIYA POSLE CHASTICHNOJ SORTIROVKI FAJLA S ISPOLXZOVANIEM SPISKOV. eSLI VOSPOLXZOVATXSYA METODAMI ALGORITMA~5.2D I UPR.~5.2-13, TO MOZHNO OBOJTISX BEZ POLEJ SVYAZI; PRI |TOM V DOPOLNENIE K PAMYATI, ZANYATOJ SAMIMI ZAPISYAMI, POTREBUETSYA VSEGO $O(\sqrt N)$~YACHEEK. eSLI ISHODNYE DANNYE RASPREDELENY RAVNOMERNO, TO SREDNEE VREMYA SORTIROVKI PROPORCIONALXNO~$N$. \excercises \rex[20] aLGORITM IZ UPR.~5.2--13 POKAZYVAET, KAK MOZHNO VYPOLNITX RASPREDELYAYUSHCHUYU SORTIROVKU, IMEYA PROSTRANSTVO PAMYATI VSEGO POD $N$~ZAPISEJ (I $M$~POLEJ SCHETCHIKOV), A NE POD $2N$~ZAPISEJ. pRIVODIT LI |TA IDEYA K USOVERSHENSTVOVANIYU ALGORITMA PORAZRYADNOJ SORTIROVKI, PROILLYUSTRIROVANNOGO V TABL.~1? \ex[13] yaVLYAETSYA LI ALGORITM~R ALGORITMOM "USTOJCHIVOJ" SORTIROVKI? %%216 \ex[15] oB®YASNITE, POCHEMU V ALGORITME~H PEREMENNOJ $|BOTM|[0]$ PRISVAIVAETSYA ZNACHENIE UKAZATELYA NA PERVUYU ZAPISX V "OB®EDINENNOJ" OCHEREDI, \emph{NESMOTRYA NA TO CHTO STOPKA 0 MOGLA BYTX PUSTOJ.} \rex[23] vO VREMYA RABOTY ALGORITMA~R VSE $M$~STOPOK HRANYATSYA V VIDE SVYAZANNYH OCHEREDEJ (PERVYM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA). iSSLEDUJTE IDEYU SVYAZYVANIYA |LEMENTOV STOPOK KAK V \emph{STEKE}. (nA RIS.~33 STRELKI POJDUT NE VVERH, A VNIZ, I TABLICA~|BOTM| STANET NE NUZHNA.) pOKAZHITE, CHTO ESLI SCEPLYATX STOPKI V SOOTVETSTVUYUSHCHEM PORYADKE, TO MOZHET POLUCHITXSYA PRAVILXNYJ METOD SORTIROVKI. bUDET LI |TOT ALGORITM BOLEE PROSTYM ILI BOLEE BYSTRYM? \ex[M24] pUSTX $g_{MN}(z)=\sum p_{MNk}z^k$, GDE $p_{MNk}$--- VEROYATNOSTX TOGO, CHTO POSLE SLUCHAJNOGO PROSMOTRA PORAZRYADNOJ SORTIROVKI, RAZLOZHIVSHEGO $N$~|LEMENTOV NA $M$~STOPOK, POLUCHILOSX ROVNO $k$~PUSTYH STOPOK. (a) pOKAZHITE, CHTO $g_{M,N+1}(z)=g_{MN}(z)+((1-z)/M)g'_{MN}(z)$. (b) nAJDITE PRI POMOSHCHI UKAZANNOGO SOOTNOSHENIYA PROSTYE VYRAZHENIYA DLYA MATEMATICHESKOGO OZHIDANIYA I DISPERSII |TOGO RASPREDELENIYA VEROYATNOSTEJ KAK FUNKCIJ OT~$M$ I~$N$. \ex[20] kAKIE IZMENENIYA NEOBHODIMO VNESTI V PROGRAMMU~R, CHTOBY ONA SORTIROVALA NE TREHBAJTOVYE KLYUCHI, A VOSXMIBAJTOVYE? sCHITAETSYA, CHTO STARSHIE BAJTY KLYUCHA~$K_i$ HRANYATSYA V YACHEJKE $|KEY|+i(1:5)$, A TRI MLADSHIH BAJTA, KAK I RANXSHE,---V YACHEJKE $|INPUT|+i(1:3)$. kAKOVO VREMYA RABOTY PROGRAMMY S |TIMI IZMENENIYAMI? \ex[20] oBSUDITE, V CHEM SOSTOIT SHODSTVO I OTLICHIE ALGORITMA~R I ALGORITMA OBMENNOJ PORAZRYADNOJ SORTIROVKI (ALGORITM~5.2.2R). \rex[20] v ALGORITMAH PORAZRYADNOJ SORTIROVKI, OBSUZHDAVSHIHSYA V TEKSTE, PREDPOLAGALOSX, CHTO VSE SORTIRUEMYE KLYUCHI NEOTRICATELXNY. kAKIE IZMENENIYA SLEDUET VNESTI V |TI ALGORITMY V TOM SLUCHAE, KOGDA KLYUCHAMI MOGUT BYTX I OTRICATELXNYE CHISLA, PREDSTAVLENNYE V \emph{DOPOLNITELXNOM ILI OBRATNOM} KODE? \ex[20] (pRODOLZHENIE UPR.~8.) kAKIE IZMENENIYA NUZHNO VNESTI V |TI ALGORITMY V SLUCHAE, KOGDA KLYUCHAMI YAVLYAYUTSYA CHISLA, PREDSTAVLENNYE V VIDE ABSOLYUTNOJ VELICHINY SO ZNAKOM? \ex[30] sKONSTRUIRUJTE ALGORITM PORAZRYADNOJ SORTIROVKI "SNACHALA-PO-STARSHEJ-CIFRE", ISPOLXZUYUSHCHIJ SVYAZANNEE RASPREDELENIE. (tAK KAK RAZMER PODFAJLOV VSE UMENXSHAETSYA, TO RAZUMNO UMENXSHITX $M$, A DLYA SORTIROVKI KOROTKIH FAJLOV PRIMENITX NE PORAZRYADNUYU SORTIROVKU.) \ex[16] pERESTANOVKA SHESTNADCATI ISHODNYH CHISEL, POKAZANNAYA V TABL.~1, SODERZHIT VNACHALE 41 INVERSIYU. pOSLE ZAVERSHENIYA SORTIROVKI INVERSIJ, RAZUMEETSYA, NET SOVSEM. sKOLXKO INVERSIJ OSTALOSX BY V FAJLE, ESLI BY MY PROPUSTILI PERVYJ PROSMOTR, A VYPOLNILI BY PORAZRYADNUYU SORTIROVKU LISHX PO CIFRAM DESYATKOV I SOTEN? sKOLXKO INVERSIJ OSTANETSYA, ESLI PROPUSTITX KAK PERVYJ, TAK I VTOROJ PROSMOTRY? \ex[24] (m. d. mAKLAREN.) pREDPOLOZHIM, ALGORITM~R PRIMENILI TOLXKO K $p$~STARSHIM CIFRAM REALXNYH KLYUCHEJ; TOGDA FAJL, ESLI CHITATX EGO PO PORYADKU, UKAZANNOMU SVYAZYAMI, POCHTI OTSORTIROVAN, NO KLYUCHI, U KOTORYH STARSHIE $p$~CIFR SOVPADAYUT, MOGUT BYTX NEUPORYADOCHENY. pRIDUMAJTE ALGORITM PERERAZMESHCHENIYA ZAPISEJ NA TOM ZHE MESTE TAK, CHTOBY KLYUCHI RASPOLOZHILISX PO PORYADKU: $K_1\le K_2\le\ldots\le K_N$. [\emph{uKAZANIE:} CHASTNYJ SLUCHAJ, KOGDA FAJL POLNOSTXYU OTSORTIROVAN, MOZHNO NAJTI V OTVETE K UPR. 5.2--12, EGO MOZHNO SKOMBINIROVATX S PROSTYMI VSTAVKAMI BEZ POTERI |FFEKTIVNOSTI, TAK KAK V FAJLE OSTALOSX MALO INVERSIJ.] \ex[40] rEALIZUJTE METOD VNUTRENNEJ SORTIROVKI, PREDLOZHENNYJ V TEKSTE V KONCE |TOGO PUNKTA, POLUCHIV PROGRAMMU SORTIROVKI SLUCHAJNYH DANNYH ZA $O(N)$~EDINIC VREMENI, TREBUYUSHCHUYU VSEGO $O(N)$ DOPOLNITELXNYH YACHEEK PAMYATI. \ex[22] pOSLEDOVATELXNOSTX IGRALXNYH KART %%217 MOZHNO OTSORTIROVATX V VOZRASTAYUSHCHEM PORYADKE: |t| |2| \dots |v| |d| |k| OT VERHNEJ KARTY K NIZHNEJ, ZA DVA PROSMOTRA, RASKLADYVAYA KARTY KAZHDYJ RAZ LISHX V DVE STOPKI: RAZLOZHITE KARTY LICEVOJ STORONOJ VNIZ V DVE STOPKI, SODERZHASHCHIE SOOTVETSTVENNO |t| |2| |9| |3| |10| I |4| |v| |5| |6| |d| |k| |7| |8| (OT NIZHNEJ KARTY K VERHNEJ); ZATEM POLOZHITE VTORUYU STOPKU POVERH PERVOJ, POVERNITE KOLODU LICEVOJ STORONOJ VVERH I RAZLOZHITE V DVE STOPKI |t| |2| |3| |4| |5| |6| |7| |8| I |9| |10| |v| |d| |k|. sOEDINITE |TI DVE STOPKI I POVERNITE IH LICEVOJ STORONOJ VVERH. kOLODA OTSORTIROVANA. dOKAZHITE, CHTO PRIVEDENNUYU VYSHE POSLEDOVATELXNOSTX KART NELXZYA OTSORTIROVATX V \emph{UBYVAYUSHCHEM} PORYADKE: |k| |d| |v| \dots |2| |t|, OT VERHNEJ KARTY K NIZHNEJ, ZA DVA PROSMOTRA, DAZHE ESLI RAZRESHENO RASKLADYVATX KARTY V TRI STOPKI. (sDAVATX KARTY, NUZHNO VSEGDA SVERHU KOLODY, POVORACHIVAYA IH PRI RAZDACHE RUBASHKOJ VVERH. nA RISUNKE VERHNYAYA KARTA KOLODY IZOBRAZHENA SPRAVA, A NIZHNYAYA---SLEVA.) \ex[m25] rASSMOTRITE ZADACHU IZ UPR.~14 V SLUCHAE, KOGDA KARTY RAZDAYUTSYA LICEVOJ STORONOJ VVERH, A NE VNIZ. tAKIM OBRAZOM, ODIN PROSMOTR MOZHNO POTRATITX NA PREOBRAZOVANIE VOZRASTAYUSHCHEGO PORYADKA V UBYVAYUSHCHIJ. sKOLXKO NUZHNO PROSMOTROV? \bigskip\epigraph kAK TOLXKO POYAVITSYA ANALITICHESKAYA MASHINA, ONA, BEZUSLOVNO, OPREDELIT DALXNEJSHIJ PUTX RAZVITIYA NAUKI. vSYAKIJ RAZ, KOGDA S EE POMOSHCHXYU BUDET NAJDEN KAKOJ-LIBO REZULXTAT, TUT ZHE VOZNIKNET VOPROS: NELXZYA LI TOT ZHE REZULXTAT POLUCHITX NA |TOJ MASHINE ZA KRATCHAJSHEE VREMYA? \signed chARLXZ b|BBIDZH (1864) %%218 \bye