\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_i0$. &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 $jK_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