7 \def\cmt{~~\color{RawSienna}}
9 \slide{Evoluce QuickSortu: Pùvodní algoritmus}
15 \:Pokud $\vert X \vert \le 1$, vrátíme $X$.
16 \:Vybereme prostøední prvek mno¾iny $X$ jako pivota $p$.
17 \:$M \leftarrow \{ x\in X : x < p \}$, \\
18 $P \leftarrow \{ x\in X : x = p \}$, \\
19 $V \leftarrow \{ x\in X : x > p \}$.
20 \:$M \leftarrow \<Sort>(M)$, \\
21 $V \leftarrow \<Sort>(V)$.
27 {\sit Èas: $\O(n\log n)$ prùmìrnì}
29 {\sit Pamì»: $\O(n)$ na~pomocná pole, $\O(n)$ na zásobník}
33 \slide{Evoluce QuickSortu: Tøídìní na místì}
35 $\<Sort>(X, a, b):$ {\cmt (setøídí prvky $X[a],\ldots,X[b]$)}
39 \:Pokud $a\ge b$, vrátíme se.
40 \:$m\leftarrow \lfloor (a+b)/2 \rfloor$, $p \leftarrow X[m]$. {\cmt (vybereme pivota)}
41 \:Pøeházíme prvky tak, aby nalevo byly $\le p$, napravo $\ge p$:
42 \::$l \leftarrow a$, $r \leftarrow b$.
43 \::Dokud $l \le r$, opakujeme:
44 \:::Dokud $X[l]<p$: $l\leftarrow l+1$.
45 \:::Dokud $X[r]>p$: $r\leftarrow r-1$.
47 \::::$X[l] \leftrightarrow X[r]$
48 \::::$l\leftarrow l+1$
49 \::::$r\leftarrow r-1$
50 \:$\<Sort>(X, a, r)$, $\<Sort>(X, l, b)$.
55 \slide{Evoluce QuickSortu: Zbavíme se rekurze}
61 \:Pokud $n=\vert X\vert \le 1$, skonèíme rovnou.
62 \:{\new $S\leftarrow\{ (1,n) \}$.} {\cmt (ná¹ vlastní zásobník)}
63 \:{\new Dokud $S\ne\emptyset$, opakujeme:}
64 \::{\new Vybereme $(a,b)$ z~$S$.}
65 \::$m\leftarrow \lfloor (a+b)/2 \rfloor$, $p \leftarrow X[m]$.
66 \::Pøeházíme prvky \dots\ $\rightarrow l,r$.
67 \::{\new Pokud $a<r$, pøidáme $(a,r)$ do~$S$.}
68 \::{\new Pokud $l<b$, pøidáme $(l,b)$ do~$S$.}
73 \slide{Evoluce QuickSortu: Omezíme spotøebu pamìti}
79 \:Pokud $n=\vert X\vert \le 1$, skonèíme rovnou.
80 \:{\new $a\leftarrow 1$, $b\leftarrow n$, $S\leftarrow\emptyset$.}
81 \:{\new Opakujeme:} {\cmt (právì tøídíme $X[a],\ldots,X[b]$, $S$ je zásobník)}
82 \::Vybereme pivota a pøeházíme prvky \dots\ $\rightarrow l,r$.
83 \::{\new Pokud $r-a > b-l$, prohodíme $(a,r) \leftrightarrow (l,b)$. \\ {\cmt (interval $(a,r)$ je teï ten men¹í)}}
84 \::{\new Pokud $r>a$:} {\cmt (oba intervaly jsou netriviální)}
85 \:::{\new Pøidáme $(l,b)$ do~$S$.} {\cmt (vìt¹í na~zásobník)}
86 \:::{\new $(a,b) \leftarrow (a,r)$.} {\cmt (pokraèujeme men¹ím)}
87 \::{\new Jinak pokud $b>l$: $(a,b) \leftarrow (l,b)$.} {\cmt (vìt¹í netriviální)}
88 \::{\new Jinak:} {\cmt (oba triviální)}
89 \:::{\new Pokud $S=\emptyset$, skonèíme.}
90 \:::{\new Jinak odebereme $(a,b)$ z~$S$.}
93 {\sit Nyní staèí $\O(\log n)$ pamìti pro zásobník.}
97 \slide{Evoluce QuickSortu: Zkøí¾íme s~InsertSortem}
99 $\<Sort>(X{\new, K}):$ {\cmt ($K$ je vhodná konstanta)}
103 \:{\new Pokud $n=\vert X\vert \le K$, setøídíme InsertSortem.}
104 \:$a=1$, $b=n$, $S=\emptyset$.
106 \::Vybereme pivota a pøeházíme prvky \dots\ $\rightarrow l,r$.
107 \::Pokud $r-a > b-l$, prohodíme $(a,r) \leftrightarrow (l,b)$.
108 \::{Pokud {\new $r-a > K$}:} {\cmt (oba intervaly jsou netriviální)}
109 \:::{Pøidáme $(l,b)$ do~$S$.} {\cmt (vìt¹í na~zásobník)}
110 \:::{$(a,b) \leftarrow (a,r)$.} {\cmt (pokraèujeme men¹ím)}
111 \::{Jinak pokud {\new $b-l > K$}: $(a,b) \leftarrow (l,b)$.} {\cmt (vìt¹í netriviální)}
112 \::{Jinak:} {\cmt (oba triviální)}
113 \:::{Pokud $S=\emptyset$, skonèíme.}
114 \:::{Jinak odebereme $(a,b)$ z~$S$.}
115 \:{\new Dotøídíme posloupnost InsertSortem.} \\ {\cmt (ka¾dý prvek se posune o~nejvý¹e~$K$, tak¾e je to lineární)}