pivot. Na toto staèí udr¾ovat si dva indexy $a$ a $b$, které znaèí, jak daleko vlevo
(vpravo) u¾ jsou správné prvky.
-Rekurzivní programy mohou být pro poèítaè zátì¾í. Proto implementujme vlastní zásobník
+Rekurzivní programy mají zbyteènì velkou re¾ii. Proto implementujme vlastní zásobník
na hranice úsekù, které zbývá setøídit. V¾dy vìt¹í interval vlo¾íme na zásobník a men¹í
-rovnou zpracujeme. Na zásobníku tedy bude maximálnì $\log n$ polo¾ek.
+rovnou zpracujeme. Na zásobníku proto bude maximálnì $\log n$ polo¾ek.
Malé podproblémy dotøídíme nìjakým triviálním algoritmem napøíklad InsertSortem.
-Odhadem pro $n=10$ je to pro dne¹ní poèítaèe výhodné.
+Odhadem pro $n=10$ je to pro dne¹ní poèítaèe výhodné (zji¹»uje se experimentálnì).
\h{Zoo tøídících algoritmù}
Porovnejme nyní známé tøídící algoritmy.
-Bude nás zajímat i jejich stabilita, tedy jestli zachovají poøadí polo¾ek se stejným
-klíèem. Stabilita je dùle¾itá pøi lexikografickém tøídìní, kde se napøed tøídí podle
-nejménì významné slo¾ky a pak podle významìj¹ích.
+\smallskip
-\s{Definice:} {\it Stabilní tøídìní} øíkáme takovému, které u~prvkù se stejnou hodnotou
+\s{Definice:} {\I Stabilní tøídìní} øíkáme takovému, které u~prvkù se stejnou hodnotou
klíèe zachová jejich vzájemné poøadí, v~jakém byly na~vstupu.
+(To se hodí napøíklad pøi lexikografickém tøídìní, kde se napøed tøídí podle
+nejménì významné slo¾ky a pak podle významìj¹ích.)
+
+\s{Definice:} Pokud tøídíme prvky {\I na místì} (tedy vstup dostaneme zadaný v~poli
+a v~tomté¾ poli pak vracíme výstup), za {\I pomocnou pamì»} tøídícího algoritmu prohlásíme
+ve¹kerou vyu¾itou pamì» mimo vstupní pole.
\medskip
\>Poznámky k tabulce:
\itemize\ibull
-\:QuickSort má jen prùmìrnou èasovou slo¾itost $\Theta (\log n)$. Mù¾eme ale øíct, ¾e
+\:QuickSort má jen prùmìrnou èasovou slo¾itost $\Theta (n\log n)$. Mù¾eme ale øíct, ¾e
porovnáváme prùmìrné èasové slo¾itosti, proto¾e u ostatních algoritmù vyjdou stejnì
jako jejich èasové slo¾itosti v~nejhor¹ím pøípadì.
\:HeapSort -- tøídìní pomocí haldy. Do haldy vlo¾íme v¹echny prvky a pak je vybereme.
-Celkem $n$ operací s haldou, ka¾dá za $\log n$. Navíc tuto haldu mohu stavìt i boøit
-v poli, ve kterém dostanu vstup.
-\:MergeSort jde implementovat s konstantní pamì»ovou slo¾itostí.
+Celkem $\Theta(n)$ operací s haldou, ka¾dá za $\Theta(\log n)$. Navíc tuto haldu mohu stavìt i
+rozebírat v~poli, ve kterém dostanu vstup.
+\:MergeSort jde implementovat s konstantní pomocnou pamìtí za cenu konstantního
+zpomalení, ov¹em konstanta je neprakticky velká.
\:MergeSort je stabilní, kdy¾ dìlím pole na poloviny. Není pøi tøídìní spojových seznamù
s~rozdìlováním prvkù na sudé a liché.
\:QuickSort se dá naprogramovat stabilnì, ale potøebuje lineárnì pomocné pamìti.
\endlist
\>®ádný algoritmus v tabulce netøídil rychleji ne¾ $\Theta(n\log n)$. To není náhoda
--- nasledující vìta nám øíká, ¾e to nejde:
+-- následující vìta nám øíká, ¾e to nejde:
-\s{Vìta:}
-Ka¾dý deterministický tøídící algoritmus zalo¾ený na porovnávání a kopírování prvkù
-potøebuje na vstup délky $n$ v nejhor¹ím pøípadì $\Omega (n \log n)$ porovnání.
+\smallskip
-O pravdìpodobnostních se v prùmìru dá dokázat podobná vìta.
+\s{Vìta:}
+Ka¾dý deterministický tøídící algoritmus, který tøídìné prvky pouze porovnává a kopíruje,
+má èasovou slo¾itost $\Omega(n\log n)$.
-\proof Bez újmy na obecnosti budeme nejdøíve pøedpokládat o algoritmu dvì vìci: Jednak
-to, ¾e algoritmus nejprve porovnává, a teprve potom kopíruje setøídìné prvky do
-výsledného pole.\foot{Algoritmus mù¾eme upravit tak, aby si pamatoval aktuální
-permutaci prvkù a podle ní prohazoval a¾ na konci.} Také pøedpokládáme, ¾e vstup
-algoritmu je permutace na mno¾inì $\{1, \ldots, n\}$. Toto je také bez újmy na
-obecnosti, proto¾e dokazujeme ¾e existuje vstup na kterém pobì¾í aspoò takhle dlouho.
+(O prùmìrné èasové slo¾itosti pravdìpodobnostních tøídících algoritmù se dá dokázat podobná vìta.)
-Chování tohoto algoritmu popí¹eme rozhodovacím stromem. V rozhodovacím stromu vnitøní
-vrcholy urèují jednotlivá porovnání prvkù a listy odpovídají okam¾ikùm, kdy algoritmus
-urèil permutaci. Porovnáváme prvky na jejich pùvodních pozicích. Nikdo nám nebrání
-porovnat prvek sám se sebou (proto mù¾e nastat rovnost) nebo porovnat nìco
-nìkolikrát\dots
+\proof
+Doká¾eme, ¾e ka¾dý porovnávací tøídící algoritmus potøebuje v~nejhor¹ím
+pøípadì provést $\Omega(n\log n)$ porovnání, co¾ dává pøirozený dolní odhad
+èasové slo¾itosti.
+
+Pøesnìji øeèeno, doká¾eme, ¾e pro ka¾dý algoritmus existuje vstup libovolné délky~$n$,
+na nìm¾ algoritmus provede $\Omega(n\log n)$ porovnání. Bez újmy na obecnosti se budeme
+zabývat pouze vstupy, které jsou permutacemi mno¾iny $\{1,\ldots, n\}$. (Staèí nám
+najít jeden \uv{tì¾ký} vstup, pokud ho najdeme mezi permutacemi, úkol jsme splnili.)
+
+Mìjme tedy deterministický algoritmus a nìjaké pevné~$n$. Sledujme, jak algoritmus
+porovnává -- u~ka¾dého porovnání zaznamenáme polohy porovnávaných prvkù tak, jak byly
+na vstupu. Jeliko¾ algoritmus je deterministický, porovná na zaèátku v¾dy tuté¾ dvojici
+prvkù. Toto porovnání mohlo dopadnout tøemi rùznými zpùsoby (vìt¹í, men¹í, rovno).
+Pro ka¾dý z~nich je opìt jednoznaènì urèeno, které prvky algoritmus porovná, a tak
+dále. Po provedení posledního porovnání algoritmus vydá jako výstup nìjakou jednoznaènì
+urèenou permutaci vstupu.
+
+Chování algoritmu proto mù¾eme popsat rozhodovacím stromem. Vnitøní vrcholy stromu odpovídají
+porovnáním prvkù, listy odpovídají vydaným permutacím. Ze~stromu vynecháme vìtve, které
+nemohou nastat (napøíklad pokud u¾ víme, ¾e $x_1<x_3$ a $x_3<x_6$, a~pøijde na øadu
+porovnání $x_1$ s~$x_6$, u¾ je jasné, jak dopadne).
+
+Poèet porovnání v~nejhor¹ím pøípadì je roven hloubce stromu. Jak ji spoèítat?
+
+V¹imneme si, ¾e pro ka¾dou z~mo¾ných permutací na vstupu musí chod algoritmu
+skonèit v~jiném listu (jinak by existovaly dvì rùzné permutace, které lze
+setøídit tými¾ prohozeními, co¾ není mo¾né). Strom tedy musí mít alespoò $n!$
+rùzných listù.
Hloubka rozhodovacího stromu odpovídá poètu porovnání. My chceme dokázat, ¾e porovnání
musí být aspoò $\Omega (n\log n)$.
-\figure{RozhodovaciStrom.eps}{Rozhodovací Strom}{0.3\hsize}
-
-Vstup je permutace $n$ prvkù, a víme ¾e poèet rùzných permutací je $n!$. Existuje tedy
-právì $n!$ rùzných vstupù. Kompletní prùbìh algoritmu je urèen pouze výsledky
-porovnání. Dále si v¹imneme, ¾e nemohou existovat dvì vstupní permutace, pro které by
-algoritmus skonèil v tém¾e listu rozhodovacího stromu. Listù stromu je tedy alespoò
-tolik, kolik je rùzných vstupù, tedy $n!$.
+% \figure{RozhodovaciStrom.eps}{Rozhodovací Strom}{0.3\hsize}
-{\narrower
+{\narrower\smallskip
\s{Lemmátko:} Ternární strom hloubky $k$ má nejvý¹e $3^k$ listù.
\par\noindent {\sl Dùkazík:} Uva¾me ternární strom hloubky $k$ s maximálním poètem
listù. V takovém stromu budou v¹echny listy urèitì le¾et na poslední hladinì
tak \uv{listnatìj¹í} strom stejné hloubky). Jeliko¾ na $i$-té hladinì je nejvý¹e $3^i$
vrcholù, v¹ech listù je nejvý¹e $3^k$.
\qed
-}
+\smallskip}
\>Z~tohoto lemmátka plyne, ¾e rozhodovací strom musí být hluboký alespoò $\log_3 n!$.
-\>Zbytek je u¾ snadné cvièení z diskrétní matematiky:
+\>Zbytek u¾ je snadné cvièení z diskrétní matematiky:
-{\narrower
+{\narrower\smallskip
\s{Lemmátko:} $ n! \ge n^{n / 2}$.
\par\noindent {\sl Dùkazík:} $n! = \sqrt{(n!)^2} = \sqrt{1(n-1)\cdot 2(n-2) \cdot \ldots \cdot n\cdot 1}$,
co¾ mù¾eme také zapsat jako $\sqrt{1(n-1)}\cdot \sqrt{2(n-2)} \cdot \ldots \cdot \sqrt{n\cdot 1}$.
Pøitom pro ka¾dé $1\le k\le n$ je $k(n+1-k) = kn + k - k^2 = n + (k-1)n + k(1-k) = n + (k-1)(n-k) \ge n$.
Proto je ka¾dá z~odmocnin vìt¹í nebo rovna $n^{1/2}$ a $n!\ge (n^{1/2})^n = n^{n/2}$.
\qed
-}
+\smallskip}
-\>Hloubka stromu tedy èiní minimálnì $\log n! \ge \log(n^{n/2}) = n/2 \cdot \log n = \Omega(n\log n)$,
-co¾ také zdola odhaduje poèet porovnání, který algoritmus provede v nejhor¹ím pøípadì.
+\>Hloubka stromu tedy èiní minimálnì $\log_3 n! \ge \log_3(n^{n/2}) = n/2 \cdot \log_3 n = \Omega(n\log n)$,
+co¾ jsme chtìli dokázat.
\qed
Ukázali jsme si tøídìní v èase $ \O(N\log{N}) $ a také dokázali, ¾e líp to v obecném
\h{Counting sort}
Counting sort je algoritmus pro tøídìní $N$ celých èísel s maximálním rozsahem hodnot
-$R$. Tøídí v èase $ \O(N + R) $ s~pamì»ovou nároèností $ \O(R) $.
+$R$. Tøídí v èase $ \Theta(N + R) $ s~pamì»ovou nároèností $ \Theta(R) $.
-Algoritmus postupnì prochází vstup a poèítá si ke ka¾dému prvku z~rozsahu kolikrát jej
-vidìl. Poté a¾ projde celý vstup, projde poèítadla a indexy u~tech, kde nìco napoèítal
-vydá jako výstup.
+Algoritmus postupnì prochází vstup a poèítá si ke ka¾dému prvku z~rozsahu, kolikrát jej
+vidìl. Poté a¾ projde celý vstup, projde poèítadla a postupnì vypí¹e v¹echna èísla z~rozsahu
+ve~správném poètu kopií.
-\s{Algoritmus:} (tøídìní posloupnosti $\left ( x_i \right )_0^N$ pomocí {\it Counting sort}u)
+\s{Algoritmus:} (tøídìní posloupnosti $x_1,\ldots,x_N\in\{1,\ldots,R\}$ pomocí {\I Counting sort}u)
\algo
-\:Pro $ i \leftarrow 1 $ do $R$ opakuj:
+\:Pro $ i = 1 \ldots R$ opakujeme:
\::$ p_i \leftarrow 0 $
-\:Pro $ i \leftarrow 1 $ do $N$ opakuj:
+\:Pro $ i = 1 \ldots N$ opakujeme:
\::$ p_{x_i} \leftarrow p_{x_i} + 1 $
\:$ j \leftarrow 1 $
-\:Pro $ i \leftarrow 1 $ do $R$ opakuj:
-\::Pokud $ p_i \neq 0 $
+\:Pro $ i = 1 \ldots R$ opakujeme:
+\::Pokud $ p_i \neq 0 $:
\:::$ v_j \leftarrow i $
\:::$ j \leftarrow j + 1 $
-\:Vra» $v$
+\:Vrátíme výsledek $v_1,\ldots,v_N$.
\endalgo
\h{Pøihrádkové tøídìní}
-Counting sort nám moc nepomù¾e, pokud chceme tøídit neco jiného ne¾ celá èísla, ale i
-to se dá øe¹it. Pøihrádkové, popøípadì kbelíkové tøídìní, neboli bucket-sort umí
-tøídit mno¾inu prvkù oèíslovaných èísly $ 1 \ldots R $.
+Counting sort nám moc nepomù¾e, pokud chceme tøídit ne pøímo celá èísla, nýbr¾
+záznamy s~celoèíselnými klíèi. Na ty se bude hodit pøihrádkové tøídìní neboli
+{\I Bucket-sort} (\uv{kbelíkové tøídìní}).
-\>Potøebuje k tomu èas $ \O(N + R) $ a pamì» $ \O(N + R) $.
+Uva¾ujme opìt~$N$ prvkù s~klíèi v~rozsahu $1,\ldots,R$. Poøídíme si~$R$ pøihrádek
+$P_1,\ldots,P_R$, prvky do nich roztøídíme a pak postupnì vypí¹eme obsah pøihrádek
+v~poøadí podle klíèù.
-Bucket sort ma je¹tì jednu pøíjemnou vlastnost: jedná se o stabilní tøídìní.
+\>Potøebujeme k tomu èas $ \Theta(N + R) $ a pamì» $ \Theta(N + R) $. Navíc se jedná
+o~stabilní algoritmus.
-\s{Algoritmus:} (tøídìní mno¾iny $x_1, x_2, \ldots, x_n $ oèíslované $c_1, c_2, \ldots, c_n$ pomocí {\it bucket-sort}u)
+\s{Algoritmus:} (tøídìní prvkù $x_1, \ldots, x_n $ s~klíèi $c_1, \ldots, c_n\in\{1,\ldots,R\}$ pomocí {\I bucket-sort}u)
\algo
-\:$P_1 \dots P_R \leftarrow \emptyset$
-\:Pro $i=1\dots n$:
-\::vlo¾ $x_i$ do $P_{x_i}$
-\:Pro $j=1\dots R$
-\::vypi¹ co je v $P_j$
+\:$P_1 \ldots P_R \leftarrow \emptyset$
+\:Pro $i=1\ldots n$:
+\::Vlo¾íme $x_i$ do $P_{c_i}$.
+\:Pro $j=1\ldots R$
+\::Vypi¹eme obsah $P_j$.
\endalgo
\h{Lexikografické tøídìní k-tic}
% a dal??
Nebo mù¾eme vyu¾ít toho, ¾e bucket-sort je stabilní a tøídit takto:
-\s{Algoritmus: } (tøídìní $k$-tic $ x_1, x_2, \ldots ,x_n $ lexikograficky pomocí {\it Bucket-sort}u)
+\s{Algoritmus: } (tøídìní $k$-tic $ x_1, \ldots ,x_n $ lexikograficky pomocí {\it Bucket-sort}u)
\algo
-\:$ S \leftarrow \{x_1, x_2, \dots, x_n\} $
-\:Pro $ i \leftarrow k $ do $ 1 $ opakuj:
-\::$ S \leftarrow $ bucket-sort $ S $ podle $i$-té souøadnice
-\:vysledek $ S $
+\:$ S \leftarrow x_1, \ldots, x_n.$
+\:Pro $ i = k $ a¾ $ 1 $ opakujeme:
+\::$ S \leftarrow $ bucket-sort $ S $ podle $i$-té souøadnice.
+\:Vydáme výsledek $S$.
\endalgo
-Pro pøehlednost v následujícím pozorování oznaème $ l = k - i + 1 $, co¾ pøesnì odpovídá tomu, v kolikátém prùchodu cyklu jsme.
+Pro pøehlednost v následujícím pozorování oznaème $ \ell = k - i + 1 $, co¾ pøesnì odpovídá tomu, v kolikátém prùchodu cyklu jsme.
\s{Pozorování:}
-Po $l$-tém prùchodu cyklem jsou prvky uspoøádány lexikograficky podle $i$-té a¾ $k$-té souøadnice.
+Po $\ell$-tém prùchodu cyklem jsou prvky uspoøádány lexikograficky podle $i$-té a¾ $k$-té souøadnice.
\proof
-Indukcí podle $l$:
+Indukcí podle $\ell$:
\itemize\ibull
-\:Pro $ l = 1 $ jsou prvky uspoøádány podle poslední souøadnice.
-\:Po $l$ prùchodech ji¾ máme prvky setøídìny lexikograficky podle $i$-té a¾ $k$-té souøadnice a spou¹tíme $(l + 1)$-ní prùchod, tj. budeme tøídít podle $(i - 1)$-ní souøadnice.
+\:Pro $ \ell = 1 $ jsou prvky uspoøádány podle poslední souøadnice.
+\:Po $\ell$ prùchodech ji¾ máme prvky setøídìny lexikograficky podle $i$-té a¾ $k$-té souøadnice a spou¹tíme $(\ell + 1)$-ní prùchod, tj. budeme tøídit podle $(i - 1)$-ní souøadnice.
Proto¾e bucket-sort tøídí stabilnì, zùstanou prvky se stejnou $(i - 1)$-ní souøadnicí vùèi sobì seøazeny tak, jak byly seøazeny na vstupu.
-Z IP tam v¹ak byly seøazeny lexikograficky podle $i$-té a¾ $k$-té souøadnice. Tudí¾ po $(l + 1)$-ním prùchodu jsou prvky seøazeny podle $(i - 1)$-ní a¾ $k$-té souøadnice.
+Z IP tam v¹ak byly seøazeny lexikograficky podle $i$-té a¾ $k$-té souøadnice. Tudí¾ po $(\ell + 1)$-ním prùchodu jsou prvky seøazeny podle $(i - 1)$-ní a¾ $k$-té souøadnice.
\endlist
\qed
-Èasová slo¾itost je $\O( k \cdot (n + R))$, co¾ je lineární s délkou vstupu $(k \cdot n)$ pro pevné $k$; pamì»ová slo¾itost èiní $\O(n + R)$.
+Èasová slo¾itost je $\Theta( k \cdot (n + R))$, co¾ je lineární s délkou vstupu $(k \cdot n)$ pro pevné $k$ a~$R$; pamì»ová slo¾itost èiní $\Theta(n + R)$.
\h{Tøídìní èísel $ 1 \ldots R $ podruhé (Radix sort)}
Zvolíme základ $Z$ a èísla zapí¹eme v soustavì o základu $Z$, èím¾ získáme $ ( \lfloor \log_z{R} \rfloor +1) $-tice, na které spustíme pøedcházející algoritmus.
-Díky tomu budeme tøídít v èase $\O({\log{R} \over \log{Z}} \cdot (n + Z))$. A jak zvolit vhodnì $Z$?
+Díky tomu budeme tøídit v èase $\Theta({\log{R} \over \log{Z}} \cdot (n + Z))$. Jak zvolit vhodné $Z$?
-Pokud bychom zvolili $Z$ konstantní, èasová slo¾itost bude $\O(\log{R} \cdot n) $, co¾ mù¾e být $ n \log{n} $ nebo i víc.
-Zvolíme-li $ Z = n $, dostáváme $ \O({\log{R} \over \log{n}} \cdot n) $, co¾ pro $ R \leq n^\alpha $ znamená $ \O(\alpha n) $.
+Pokud bychom zvolili $Z$ konstantní, èasová slo¾itost bude $\Theta(\log{R} \cdot n) $, co¾ mù¾e být $ n \log{n} $ nebo i víc.
+Zvolíme-li $ Z = n $, dostáváme $ \Theta({\log{R} \over \log{n}} \cdot n) $, co¾ pro $ R \leq n^\alpha $ znamená $ \O(\alpha n) $.
+Polynomiálnì velká celá èísla jde tedy tøídit v~lineárním èase.
\h{Tøídìní øetìzcù}
\>{\I (Na pøedná¹ce letos nebylo, ale pro úplnost uvádíme.)}
-Mìjme $n$ øetìzcù $ r_1, r_2 \dots r_n $ dlouhých $ l_1, l_2 \dots
+Mìjme $n$ øetìzcù $ r_1, r_2 \ldots r_n $ dlouhých $ l_1, l_2 \ldots
l_n $ Oznaème si $ L = \max_{1 \leq i \leq n} l_i $ délku nejdel¹ího øetìzce a $R$
poèet znakù abecedy.
Problém je, ¾e øetìzce nemusí být stejnì dlouhé (pokud by byly, lze se na øetìzce
-dívat jako na $k$-tice, které u¾ tøídít umíme). S tím se mù¾eme pokusit vypoøádat
+dívat jako na $k$-tice, které u¾ tøídit umíme). S tím se mù¾eme pokusit vypoøádat
doplnìním øetìzcù mezerami tak, aby mìly v¹echny stejnou délku, a spustit na nìj
algoritmus pro $k$-tice. Tím dostaneme algoritmus, který bude mít èasovou slo¾itost $
\O(Ln) $, co¾ bohu¾el mù¾e být a¾ kvadratické vzhledem k velikosti vstupu.
\+ HeapSort & $\Theta (n\log n)$ & $\Theta (1)$ & $-$ \cr
\+ QuickSort & $\Theta (n\log n)$ & $\Theta (\log n)$ & $-$ \cr
\+ BucketSort & $\Theta (n+R)$ & $\Theta (n+R)$ & $+$ \cr
-\+ k-tice & $\Theta (k(n+R))$ & $\Theta (n+R)$ & $+$ \cr
+\+ $k$-tice & $\Theta (k(n+R))$ & $\Theta (n+R)$ & $+$ \cr
\+ RadixSort & $\Theta (n\log _n R)$ & $\Theta (n)$ & $+$ \cr
\smallskip
mno¾inì, konkrétnì v èase $ \O(\log n) $ napø. pomocí pùlení intervalù. Dal¹ím
problémem, na který se hodí pou¾ít tøídìní, je zji¹tìní, zda se v posloupnosti nìjaké
její hodnoty opakují. Dá se dokázat, ¾e tuto úlohu nelze vyøe¹it lépe (rychleji), ne¾
-tak, ¾e hodnoty nejprve setøídíme a poté setøidìnou posloupnost projdeme.
+tak, ¾e hodnoty nejprve setøídíme a poté setøídìnou posloupnost projdeme.
\h{Násobení matic n$\times$n a Strassenùv algoritmus}
projects / ads1.git / blobdiff