\input style
\chapnotrue
\chapno=5
\subchno=1
%% 93
\subchap{vNUTRENNYAYA SORTIROVKA}
nACHNEM OBSUZHDENIE HOROSHEGO "SORTIROVANIYA" S MALENXKOGO |KSPERIMENTA: KAK 
BY VY RESHILI SLEDUYUSHCHUYU ZADACHU PROGRAMMIROVANIYA?                    $$
\vtop{
\narrower
"yaCHEJKI PAMYATI $|R|+1$,  $|R|+2$, $|R|+3$, $|R|+4$ I~$|R|+5$
SODERZHAT PYATX CHISEL. nAPISHITE PROGRAMMU, KOTORAYA PERERAZMESHCHAET, ESLI NUZHNO,
 |TI CHISLA TAK, CHTOBY ONI RASPOLOZHILISX V VOZRASTAYUSHCHEM PORYADKE."
\par
}
$$
(eSLI VY UZHE ZNAKOMY S KAKIMI-LIBO METODAMI SORTIROVKI, POSTARAJTESX, 
POZHALUJSTA, NA MINUTU ZABYTX O NIH; VOOBRAZITE, CHTO VY RESHAETE TAKUYU 
ZADACHU VPERVYE, NE IMEYA NIKAKIH PREDVARITELXNYH ZNANIJ O TOM, KAK K NEJ PODSTUPITXSYA.)

\bigskip
\emph{
pREZHDE CHEM CHITATX DALXSHE, NASTOYATELXNO PROSIM VAS NAJTI HOTX KAKOE-NIBUDX 
RESHENIE |TOJ ZADACHI.
}
\bigskip
\line{\null\leaders\hbox to 1em{\hss.\hss}\hfill\null}
\bigskip

vREMYA, ZATRACHENNOE NA RESHENIE PRIVEDENNOJ VYSHE ZADACHI, OKUPITSYA S LIHVOJ, 
KOGDA VY PRODOLZHITE CHTENIE |TOJ GLAVY. vOZMOZHNO, VASHE RESHENIE OKAZHETSYA 
ODNIM IZ SLEDUYUSHCHIH:

\medskip
A.{\sl  sORTIROVKA VSTAVKAMI.\/} eLEMENTY PROSMATRIVAYUTSYA PO ODNOMU, I 
KAZHDYJ NOVYJ |LEMENT VSTAVLYAETSYA V PODHODYASHCHEE MESTO SREDI RANEE 
UPORYADOCHENNYH |LEMENTOV. (iMENNO TAKIM SPOSOBOM IGROKI V BRIDZH 
UPORYADOCHIVAYUT SVOI KARTY, BERYA PO ODNOJ.)

B.{\sl  oBMENNAYA SORTIROVKA.\/} eSLI DVA |LEMENTA RASPOLOZHENY NE PO 
PORYADKU, TO ONI MENYAYUTSYA MESTAMI. eTOT PROCESS POVTORYAETSYA DO TEH POR, 
POKA |LEMENTY NE BUDUT UPORYADOCHENY.
 C. {\sl sORTIROVKA POSREDSTVOM VYBORA.\/} sNACHALA VYDELYAETSYA 
NAIMENXSHIJ (ILI. BYTX MOZHET, NAIBOLXSHIJ) |LEMENT I KAKIM-LIBO OBRAZOM 
OTDELYAETSYA OT OSTALXNYH, ZATEM VYBIRAETSYA NAIMENXSHIJ (NAIBOLXSHIJ) IZ 
OSTAVSHIHSYA I T. D.

D. {\sl sORTIROVKA PODSCHETOM.\/} kAZHDYJ |LEMENT SRAVNIVAETSYA SO VSEMI 
OSTALXNYMI; OKONCHATELXNOE-POLOZHENIE |LEMENTA OPREDELYAETSYA PODSCHETOM 
CHISLA MENXSHIH KLYUCHEJ.

E. {\sl sPECIALXNAYA SORTIROVKA\/}, KOTORAYA HOROSHA DLYA PYATI |LEMENTOV, 
UKAZANNYH V ZADACHE, NO NE PODDAETSYA PROSTOMU OBOBSHCHENIYU NA. SLUCHAJ 
BOLXSHEGO CHISLA |LEMENTOV.
%% 94
F. {\sl lENIVOE RESHENIE.\/} vY NE OTKLIKNULISX NA NASHE PREDLOZHENIE I 
OTKAZALISX RESHATX ZADACHU. zhALX, NO TEPERX, KOGDA VY PROCHLI TAK MNOGO, VASH 
SHANS UPUSHCHEN.

G. {\sl nOVAYA SUPERSORTIROVKA\/}, KOTORAYA PREDSTAVLYAET SOBOJ 
OPREDELENNOE USOVERSHENSTVOVANIE IZVESTNYH METODOV. (pOZHALUJSTA,
 NEMEDLENNO SOOBSHCHITE OB |TOM AVTORU.)
\medskip

eSLI BY |TA ZADACHA BYLA SFORMULIROVANA, SKAZHEM, DLYA 1000 |LEMENTOV, A NE 
DLYA 5, TO VY MOGLI BY OTKRYTX I NEKOTORYE BOLEE TONKIE METODY, O KOTORYH 
BUDET UPOMYANUTO NIZHE. v LYUBOM SLUCHAE, PRISTUPAYA K NOVOJ ZADACHE, RAZUMNO 
NAJTI KAKUYU-NIBUDX OCHEVIDNUYU PROCEDURU, A ZATEM POPYTATXSYA ULUCHSHITX 
EE. sLUCHAI a, v I s PRIVODYAT K VAZHNYM KLASSAM METODOV SORTIROVKI, 
KOTORYE PREDSTAVLYAYUT SOBOJ USOVERSHENSTVOVANIYA SFORMULIROVANNYH VYSHE 
PROSTYH IDEJ.

bYLO IZOBRETENO MNOZHESTVO RAZLICHNYH ALGORITMOV SORTIROVKI, I V |TOJ 
KNIGE RASSMATRIVAETSYA OKOLO 25 IZ NIH. eTO PUGAYUSHCHEE KOLICHESTVE METODOV NA 
SAMOM DELE LISHX MALAYA TOLIKA VSEH ALGORITMOV, PRIDUMANNYH DO SIH POR; 
MNOGIE, UZHE USTAREVSHIE METODY MY VOVSE NE BUDEM RASSMATRIVATX ILI 
UPOMYANEM LISHX VSKOLXZX. pOCHEMU ZHE TAK MNOGO METODOV SORTIROVKI? 
dLYA PROGRAMMIROVANIYA |TO CHASTNYJ SLUCHAJ VOPROSA: "pOCHEMU SUSHCHESTVUET TAK 
MNOGO METODOV $x$?", GDE $x$ PROBEGAET MNOZHESTVO VSEH ZADACH. oTVET SOSTOIT 
V TOM, CHTO KAZHDYJ METOD IMEET SVOI PREIMUSHCHESTVA I NEDOSTATKI, PO|TOMU ON 
OKAZYVAETSYA |FFEKTIVNEE DRUGIH PRI NEKOTORYH KONFIGURACIYAH DANNYH I 
APPARATURY. k SOZHALENIYU, NEIZVESTEN "NAILUCHSHIJ" SPOSOB SORTIROVKI;
SUSHCHESTVUET \emph{MNOGO} NAILUCHSHIH METODOV V ZAVISIMOSTI OT TOGO, CHTO 
SORTIRUETSYA, NA KAKOJ MASHINE, DLYA KAKOJ CELI. gOVORYA SLOVAMI rEDXYARDA 
kIPLINGA, "SUSHCHESTVUET 9 I ESHCHE 60 SPOSOBOV SLOZHITX PESNYU PLEMENI, I KAZHDYJ 
IZ NIH V OTDELXNOSTI HOROSH".

pOLEZNO IZUCHITX HARAKTERISTIKI KAZHDOGO METODA SORTIROVKI, CHTOBY MOZHNO BYLO 
PROIZVODITX RAZUMNYJ VYBOR DLYA KONKRETNYH PRILOZHENIJ. k SCHASTXYU, ZADACHA 
IZUCHENIYA |TIH ALGORITMOV NE STOLX UZH GROMOZDKA, POSKOLXKU MEZHDU NIMI 
SUSHCHESTVUYUT INTERESNYE VZAIMOSVYAZI.

v NACHALE |TOJ GLAVY MY VVELI OSNOVNUYU TERMINOLOGIYU I OBOZNACHENIYA, KOTORYE 
I BUDEM ISPOLXZOVATX PRI IZUCHENII SORTIROVKI. zAPISI
$$
R_1, R_2, \ldots, R_N
\eqno(1)
$$
DOLZHNY BYTX OTSORTIROVANY V NEUBYVAYUSHCHEM PORYADKE PO SVOIM KLYUCHAM $K_1$, 
$K_2$, \dots, $K_N$, PO SUSHCHESTVU, PUTEM NAHOZHDENIYA PERESTANOVKI $p(1)$ 
$p(2)$ \dots $p(N)$,  TAKOJ, CHTO
$$
K_{p(1)}\le K_{p(2)}\le \ldots \le K_{p(N)}.
\eqno(2)
$$
%% 95
v |TOM PARAGRAFE RASSMATRIVAETSYA \dfn{VNUTRENNYAYA SORTIROVKA}, KOGDA CHISLO 
ZAPISEJ, PODLEZHASHCHIH SORTIROVKE, DOSTATOCHNO MALO, TAK CHTO VESX PROCESS 
MOZHNO PROVESTI V OPERATIVNOJ PAMYATI evm.

v ODNIH SLUCHAYAH MOZHET PONADOBITXSYA FIZICHESKI PERERAZMESTITX ZAPISI V 
PAMYATI TAK, CHTOBY IH KLYUCHI BYLI UPORYADOCHENY;
V DRUGIH MOZHNO OBOJTISX VSPOMOGATELXNOJ TABLICEJ NEKOTOROGO
\picture{rIS. 6. sORTIROVKA TABLICY ADRESOV.}
VIDA, KOTORAYA OPREDELYAET PERESTANOVKU. eSLI ZAPISI I/ILI KLYUCHI ZANIMAYUT 
NESKOLXKO SLOV PAMYATI, TO CHASTO LUCHSHE SOSTAVITX NOVUYU TABLICU ADRESOV 
(SSYLOK), KOTORYE UKAZYVAYUT NA ZAPISI, I RABOTATX S |TIMI ADRESAMI, NE 
PEREMESHCHAYA GROMOZDKIE ZAPISI. tAKOJ METOD NAZYVAETSYA \dfn{SORTIROVKOJ 
TABLICY ADRESOV}
\picture{rIS. 7.  sORTIROVKA SPISKA.}
(RIS~ 6.). eSLI KLYUCHI KOROTKIE, A SOPUTSTVUYUSHCHAYA INFORMACIYA V ZAPISYAH 
VELIKA, TO DLYA POVYSHENIYA SKOROSTI KLYUCHI MOZHNO VYNESTI V TABLICU ADRESOV; 
|TO NAZYVAETSYA \dfn{SORTIROVKOJ KLYUCHEJ}. dRUGIE SHEMY SORTIROVKI 
ISPOLXZUYUT VSPOMOGATELXNOE POLE SVYAZI, KOTOROE VKLYUCHAETSYA V KAZHDUYU ZAPISX. 
sVYAZI OBRABATYVAYUTSYA TAKIM OBRAZOM, CHTO V REZULXTATE VSE ZAPISI 
OKAZYVAYUTSYA SVYAZANNYMI V LINEJNYJ SPISOK, V KOTOROM KAZHDAYA SVYAZX 
UKAZYVAET NA SLEDUYUSHCHUYU PO PORYADKU ZAPISX. eTO NAZYVAETSYA 
\dfn{SORTIROVKOJ SPISKA} (RIS. 7).

%% 96

pOSLE SORTIROVKI TABLICY ADRESOV ILI SORTIROVKI SPISKA MOZHNO PO ZHELANIYU 
RASPOLOZHITX ZAPISI V NEUBYVAYUSHCHEM PORYADKE. dLYA |TOGO IMEETSYA NESKOLXKO 
SPOSOBOV, TREBUYUSHCHIH DOPOLNITELXNOJ PAMYATI DLYA HRANENIYA VSEGO ODNOJ ZAPISI 
(SM. UPR. S 10 PO 12);
ILI ZHE MOZHNO PROSTO PEREMESTITX ZAPISI V NOVUYU OBLASTX PAMYATI,  ESLI ONA 
MOZHET VMESTITX VSE |TI ZAPISI. pOSLEDNIJ SPOSOB OBYCHNO VDVOE BYSTREE 
PERVOGO, NO TREBUET POCHTI V DVA RAZA BOLXSHE PAMYATI. vO MNOGIH PRILOZHENIYAH 
VOVSE NE OBYAZATELXNO PEREMESHCHATX ZAPISI, TAK KAK POLYA SVYAZI, KAK PRAVILO, 
VPOLNE PRIEMLEMY DLYA OPERACIJ S POSLEDOVATELXNOJ ADRESACIEJ.

vSE METODY SORTIROVKI, KOTORYE MY ISSLEDUEM "DOSKONALXNO", BUDUT 
PROILLYUSTRIROVANY CHETYRXMYA SPOSOBAMI: POSREDSTVOM
\medskip
\item{a)} SLOVESNOGO OPISANIYA ALGORITMA,
\item{b)} BLOK-SHEMY,
\item{c)} PROGRAMMY DLYA MASHINY \MIX,
\item{d)} PRIMERA PRIMENENIYA |TOGO METODA SORTIROVKI K ZADANNOMU MNOZHESTVU CHISEL.
\medskip
[v TEH PRIMERAH, GDE |TO UMESTNO, BUDET OBRABATYVATXSYA MNOZHESTVO IZ 16 
CHISEL, KOTORYE AVTOR, POLXZUYASX NABOROM DESYATICHNYH IGRALXNYH KOSTEJ, 
VYBRAL SLUCHAJNYM OBRAZOM 19 MARTA 1963 G.; SR. S UPR. 3.1--1 (S).]

iZ SOOBRAZHENIJ UDOBSTVA PROGRAMMY DLYA MASHINY \MIX\ BUDUT, KAK PRAVILO, 
NAPISANY V PREDPOLOZHENII, CHTO KLYUCH CHISLOVOJ I CHTO ON POMESHCHAETSYA V ODNOM 
SLOVE; INOGDA MY DAZHE BUDEM OGRANICHIVATX ZNACHENIYA KLYUCHEJ TAK, CHTOBY ONI 
ZANIMALI LISHX CHASTX SLOVA. oTNOSHENIEM PORYADKA $<$ BUDET OBYCHNOE 
ARIFMETICHESKOE OTNOSHENIE PORYADKA, A ZAPISI BUDUT SOSTOYATX IZ ODNOGO 
KLYUCHA, BEZ SOPUTSTVUYUSHCHEJ INFORMACII. v |TIH PREDPOLOZHENIYAH 
PROGRAMMY POLUCHAYUTSYA KOROCHE, PROSHCHE DLYA PONIMANIYA, I NE PREDSTAVLYAET TRUDA 
RASPROSTRANITX IH NA OBSHCHIJ SLUCHAJ (NAPRIMER, PRIMENYAYA SORTIROVKU TABLIC 
ADRESOV). vMESTE S \MIX-PROGRAMMAMI PRIVODITSYA ANALIZ VREMENI VYPOLNENIYA 
SOOTVETSTVUYUSHCHEGO ALGORITMA SORTIROVKI.

\section sORTIROVKA PODSCHETOM. chTOBY PROILLYUSTRIROVATX SPOSOB, KOTORYM 
MY BUDEM IZUCHATX METODY VNUTRENNEJ SORTIROVKI, RASSMOTRIM IDEYU 
"PODSCHETA", UPOMYANUTUYU V NACHALE |TOGO PARAGRAFA. eTOT PROSTOJ METOD 
OSNOVAN NA TOM, CHTO $j$-J KLYUCH V OKONCHATELXNO UPORYADOCHENNOJ 
POSLEDOVATELXNOSTI PREVYSHAET ROVNO $(j-1)$ IZ OSTALXNYH KLYUCHEJ. iNACHE 
GOVORYA, ESLI IZVESTNO, CHTO NEKOTORYJ KLYUCH PREVYSHAET ROVNO 27 DRUGIH, TO 
POSLE SORTIROVKI SOOTVETSTVUYUSHCHAYA ZAPISX DOLZHNA ZANYATX 28-E MESTO. tAKIM 
OBRAZOM, IDEYA SOSTOIT V TOM, CHTOBY SRAVNITX POPARNO VSE KLYUCHI I 
PODSCHITATX, SKOLXKO IZ NIH MENXSHE KAZHDOGO OTDELXNOGO KLYUCHA.

%% 97

oCHEVIDNYJ SPOSOB VYPOLNITX SRAVNENIYA---
$$
\hfill
\hbox{((SRAVNITX $K_j$ c $K_i$) PRI $1\le j \le N$) PRI $1\le i\le N$,}
\hfill
$$
NO LEGKO VIDETX, CHTO BOLEE POLOVINY |TIH DEJSTVIJ IZLISHNI, POSKOLXKU NE 
NUZHNO SRAVNIVATX KLYUCH SAM S SOBOJ I POSLE SRAVNENIYA $K_a$ S $K_b$ UZHE NE 
NADO SRAVNIVATX $K_b$ S $K_a$. pO|TOMU DOSTATOCHNO
$$
\hfill
\hbox{((SRAVNITX $K_j$ S $K_i$) PRI $1\le j\le i$) PRI $1 < i \le N$.}
\hfill
$$
iTAK, PRIHODIM K SLEDUYUSHCHEMU ALGORITMU.

\alg s.(sRAVNENIE I PODSCHET.) eTOT ALGORITM SORTIRUET ZAPISI 
$R_1$,~\dots, $R_N$ PO KLYUCHAM $K_1$,~\dots, $K_N$, ISPOLXZUYA DLYA 
PODSCHETA CHISLA KLYUCHEJ, MENXSHIH DANNOGO, VSPOMOGATELXNUYU TABLICU 
$|COUNT|[1]$,~\dots, $|COUNT|[N]$. pOSLE ZAVERSHENIYA ALGORITMA VELICHINA 
$|COUNT|[j]+1$ OPREDELYAET OKONCHATELXNOE POLOZHENIE ZAPISI $R_j$.

\st[sBROSITX SCHETCHIKI.] uSTANOVITX $|COUNT|[1]$,~\dots, $|COUNT|[N]$
RAVNYMI NULYU.

\st[cIKL PO $i$.] vYPOLNITX SHAG \stp{z} PRI $i=N$, $N-1$, \dots, 2;
ZATEM ZAVERSHITX RABOTU ALGORITMA.

\st[cIKL PO $j$.] vYPOLNITX SHAG \stp{4} PRI $j=i -1$, $i-2$, \dots, 1.

\st[sRAVNITX $K_i$, $K_j$.] eSLI $K_i<K_j$, TO UVELICHITX $|COUNT|[j]$ NA 
1; V PROTIVNOM SLUCHAE UVELICHITX $|COUNT|[i]$ NA~1.
\algend

zAMETIM, CHTO V |TOM ALGORITME ZAPISI NE PEREMESHCHAYUTSYA. oN ANALOGICHEN 
SORTIROVKE TABLICY ADRESOV, POSKOLXKU TABLICA |COUNT| OPREDELYAET KONECHNOE 
RASPOLOZHENIE ZAPISEJ; NO |TI
METODY NESKOLXKO RAZLICHAYUTSYA, POTOMU CHTO $|COUNT|[j]$ UKAZYVAET TO MESTO, 
KUDA NUZHNO PERESLATX ZAPISX $R_j$, A NE TU ZAPISX, KOTORUYU NADO PERESLATX 
NA MESTO $R_j$. (tAKIM OBRAZOM, TABLICA |COUNT| OPREDELYAET PERESTANOVKU, 
OBRATNUYU $p(1)$~\dots $p(n)$; SM. P.~5.1.1.)

v RASSUZHDENII, PREDSHESTVUYUSHCHEM |TOMU ALGORITMU, MY NE UCHITYVALI, CHTO KLYUCHI 
MOGUT BYTX RAVNYMI. eTO, VOOBSHCHE GOVORYA, SERXEZNOE UPUSHCHENIE, POTOMU CHTO 
ESLI BY RAVNYM KLYUCHAM SOOTVETSTVOVALI RAVNYE SCHETCHIKI, TO ZAKLYUCHITELXNOE 
PEREMESHCHENIE ZAPISEJ BYLO BY DOVOLXNO SLOZHNYM. k SCHASTXYU, KAK POKAZANO V 
UPR. 2, ALGORITM C DAET VERNYJ REZULXTAT NEZAVISIMO OT CHISLA RAVNYH KLYUCHEJ.
\picture{rIS. 8. aLGORITM s: SRAVNENIE I PODSCHET.}

%% 98

\ctable{|COUNT|($#$):\hfill&&\bskip\hfill$#$\hfill\bskip\cr
\noalign{\rightline{tABLICA 1}}
\noalign{\centerline{\bf sORTIROVKA PODSCHETOM (ALGORITM s)}}
\noalign{\vskip0.5ex\hrule\vskip0.5ex}
\omit \hfill KLYUCHI: \hfill
           & 503 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 & 154 & 509 & 612 & 677 & 765 & 703\cr
\hbox{NACH.}&  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0 \cr
i=N        &  0  &  0  &  0  &  0  &  1  &  0  &  1  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  1  &  12\cr
i=N-1      &  0  &  0  &  0  &  0  &  2  &  0  &  2  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  13 &  12\cr
i =N-2     &  0  &  0  &  0  &  0  &  3  &  0  &  3  &  0  &  0  &  0  &  0  &  0  &  0  &  11 &  13 &  12\cr
i=N-3      &  0  &  0  &  0  &  0  &  4  &  0  &  4  &  0  &  1  &  0  &  0  &  0  &  9  &  11 &  13 &  12\cr
i=N-4      &  0  &  0  &  1  &  0  &  5  &  0  &  5  &  0  &  2  &  0  &  0  &  7  &  9  &  11 &  13 &  12\cr
i=N-5      &  1  &  0  &  2  &  0  &  6  &  1  &  6  &  1  &  3  &  1  &  2  &  7  &  9  &  11 &  13 &  12\cr
\noalign{
\line{\null\leaders\hbox to 1em{\hss.\hss}\hfill\null}
}
i=2        &  6  &  1  &  8  &  0  &  15 &  3  &  14 &  4  &  10 &  5  &  2  &  7  &  9  &  11 &  13 &  12\cr
\noalign{\vskip0.5ex\hrule\vskip0.5ex}
}

\prog C.(sRAVNENIE I PODSCHET.) v SLEDUYUSHCHEJ REALIZACII ALGORITMA C DLYA 
MASHINY \MIX\ PREDPOLAGAETSYA, CHTO ZAPISX $R_j$ NAHODITSYA V YACHEJKE 
$|INPUT|+j$, a $|COUNT|[j]$---V YACHEJKE $|COUNT| +j$, GDE $1\le j\le N$; 
$|rI1|\equiv i$; $|rI2|\equiv j$; $|rA|\equiv K_i\equiv R_i$; 
$|rX|\equiv|COUNT|[i]$.
\code
START&ENT1 & N       & 1  &s1 . sBROSITX SCHETCHIKI.
     &STZ  & COUNT,1 & N  &$|COUNT|[i]\asg 0$.
     &DEC1 & 1       & N
     &J1P  & *-2     & N  &$N\ge i>0$.
     &ENT1 & N       & 1  &s2. cIKL PO $i$.
     &JMP  & 1F      & 1 
2n   &LDA  & INPUT,1 & N-1
     &LDX  & COUNT,1 & N-1
3H   &CMPA & INPUT,2 & A   &C4. sRAVNITX $K_i$, $K_j$.
     &JGE  & 4F      & A   &pEREHOD, ESLI $K_i\ge K_j$.
     &LD3  & COUNT,2 & B   &$|COUNT|[j]$
     &INC3 & 1       & B   &$+1$
     &ST3  & COUNT,2 & B   &$\to |COUNT|[j]$
     &JMP  & 5F      & B   
4H   &INCX & 1       & A-B &$|COUNT|[i]+1\to|COUNT|[i]$.
5H   &DEC2 & 1       & A   &s3.cIKL PO $j$.
     &J2P  & 3B      & A
     &STX  & COUNT,1 & N-1
     &DEC1 & 1       & N-1
1n   &ENT2 & -1,1    & N   &$N\ge i>j>0$.
     &J2P  & 2B      & N
\endcode
\progend

vREMYA RABOTY |TOJ PROGRAMMY RAVNO $13N+6A+5B-4$ EDINIC, GDE $N$---CHISLO 
ZAPISEJ,  $A$---CHISLO SPOSOBOV VYBRATX 2 PREDMETA IZ $N$, T. E. 
$\perm{N}{2}=(N^2-N)/2$, A $B$--- CHISLO PAR INDEKSOV,
TAKIH, CHTO $j<i$, I $K_j>K_i$. tAKIM OBRAZOM, $B$---\emph{CHISLO INVERSIJ} 
PERESTANOVKI $K_1$, \dots, $K_N$; |TA VELICHINA PODROBNO ANALIZIROVALASX 
V P.~5.1.1, I BYLO NAJDENO [FORMULY (5.1.1--12,13)], CHTO DLYA NERAVNYH 
KLYUCHEJ, RASPOLOZHENNYH V SLUCHAJNOM PORYADKE,
$$
B=\left(\min 0, \ave {(N^2-N\over 4}, \max{(N^2-N)\over 2}, 
\dev{\sqrt{N(N-1)(N+2.5)}\over 6}\right).
$$

%% 99

sLEDOVATELXNO, VYPOLNENIE PROGRAMMY C ZANIMAET 
OT~$3N^2+10N-4$ DO~$5.5N^2+7.5N-4$ EDINIC VREMENI, A SREDNEE VREMYA RABOTY 
NAHODITSYA POSEREDINE MEZHDU |TIMI DVUMYA GRANICAMI. nAPRIMER, DLYA DANNYH 
TABL.~1 IMEEM $N=16$, $A=120$, $B=41$, ZNACHIT, PROGRAMMA C OTSORTIRUET IH 
ZA VREMYA $1129u$. mODIFIKACIYU PROGRAMMY $C$, OBLADAYUSHCHUYU NESKOLXKO INYMI 
VREMENNYMI HARAKTERISTIKAMI, SM. V UPR.~5.

mNOZHITELX $N^2$, KOTORYM OPREDELYAETSYA VREMYA RABOTY, SVIDETELXSTVUET O 
TOM, CHTO ALGORITM C NE DAET |FFEKTIVNOGO SPOSOBA SORTIROVKI, KOGDA $N$ 
VELIKO; PRI UDVOENII CHISLA ZAPISEJ VREMYA UVELICHIVAETSYA V CHETYRE RAZA. 
pOSKOLXKU |TOT METOD TREBUET SRAVNENIYA VSEH PAR KLYUCHEJ $(K_i, K_j)$, TO 
NET OCHEVIDNOGO SPOSOBA ISKLYUCHITX ZAVISIMOSTX OT $N^2$, TEM NE MENEE MY 
UVIDIM DALXSHE V |TOJ GLAVE, CHTO, POLXZUYASX "RAZDELENIEM I OBMENOM", 
MOZHNO SNIZITX PORYADOK SREDNEGO VREMENI RABOTY DO $N\log N$. aLGORITM C 
INTERESEN DLYA NAS NE |FFEKTIVNOSTXYU, A GLAVNYM OBRAZOM SVOEJ PROSTOTOJ; 
EGO OPISANIE SLUZHIT PRIMEROM TOGO STILYA, V KOTOROM BUDUT OPISANY BOLEE 
SLOZHNYE (I BOLEE |FFEKTIVNYE) METODY.

sUSHCHESTVUET DRUGAYA RAZNOVIDNOSTX SORTIROVKI POSREDSTVOM PODSCHETA, KOTORAYA 
\emph{DEJSTVITELXNO} VESXMA VAZHNA S TOCHKI ZRENIYA |FFEKTIVNOSTI; ONA 
PRIMENIMA V OSNOVNOM V TOM SLUCHAE, KOGDA IMEETSYA MNOGO RAVNYH KLYUCHEJ I VSE 
ONI POPADAYUT V DIAPAZON $u\le K_j\le v$, GDE ZNACHENIE $(v-u)$ NEVELIKO. 
eTI PREDPOLOZHENIYA PREDSTAVLYAYUTSYA VESXMA OGRANICHITELXNYMI, NO NA,SAMOM DELE 
MY UVIDIM NEMALO PRILOZHENIJ |TOJ IDEI; NAPRIMER, ESLI PRIMENITX |TOT 
METOD LISHX K STARSHIM CIFRAM KLYUCHEJ, A NE KO VSEM KLYUCHAM CELIKOM, TO FAJL 
OKAZHETSYA CHASTICHNO OTSORTIROVANNYM, I BUDET UZHE SRAVNITELXNO PROSTO DOVESTI 
DELO DO KONCA.

chTOBY PONYATX PRINCIP, PREDPOLOZHIM, CHTO VSE KLYUCHI LEZHAT MEZHDU~1 I~100. pRI 
PERVOM PROSMOTRE FAJLA MOZHNO PODSCHITATX, SKOLXKO IMEETSYA KLYUCHEJ, RAVNYH 
1, 2, \dots, 100, A PRI VTOROM PROSMOTRE MOZHNO UZHE RASPOLAGATX ZAPISI V 
SOOTVETSTVUYUSHCHIH MESTAH OBLASTI VYVODA. v SLEDUYUSHCHEM ALGORITME VSE 
|TO OPISANO BOLEE PODROBNO.
\picture{rIS. 9. aLGORITM D: RASPREDELYAYUSHCHIJ PODSCHET.}
%% 100

\bye