\language=\czech
\chyph
+\def\new{\color{Blue}}
+\def\cmt{~~\color{RawSienna}}
+
\slide{Evoluce QuickSortu: Pùvodní algoritmus}
$\<Sort>(X):$
\algo
+\itemcount=-1
\:Pokud $\vert X \vert \le 1$, vrátíme $X$.
-\:Vybereme prostøední prvek~$X$ jako pivota $p$.
+\:Vybereme prostøední prvek mno¾iny $X$ jako pivota $p$.
\:$M \leftarrow \{ x\in X : x < p \}$, \\
$P \leftarrow \{ x\in X : x = p \}$, \\
$V \leftarrow \{ x\in X : x > p \}$.
\:Vrátíme $M+P+V$.
\endalgo
+\bigskip
+
+{\sit Èas: $\O(n\log n)$ prùmìrnì}
+
+{\sit Pamì»: $\O(n)$ na~pomocná pole, $\O(n)$ na zásobník}
+
\endslide
\slide{Evoluce QuickSortu: Tøídìní na místì}
-$\<Sort>(X, a, b):$
+$\<Sort>(X, a, b):$ {\cmt (setøídí prvky $X[a],\ldots,X[b]$)}
\algo
+\itemcount=-1
\:Pokud $a\ge b$, vrátíme se.
-\:$m\leftarrow \lfloor (a+b)/2 \rfloor$, $p \leftarrow X[m]$.
+\:$m\leftarrow \lfloor (a+b)/2 \rfloor$, $p \leftarrow X[m]$. {\cmt (vybereme pivota)}
\:Pøeházíme prvky tak, aby nalevo byly $\le p$, napravo $\ge p$:
\::$l \leftarrow a$, $r \leftarrow b$.
\::Dokud $l \le r$, opakujeme:
\:::Dokud $X[l]<p$: $l\leftarrow l+1$.
\:::Dokud $X[r]>p$: $r\leftarrow r-1$.
-\:::$X[l] \leftrightarrow X[r]$.
-\:::$l\leftarrow l+1$, $r\leftarrow r-1$.
+\:::Je-li $l\le r$:
+\::::$X[l] \leftrightarrow X[r]$
+\::::$l\leftarrow l+1$
+\::::$r\leftarrow r-1$
\:$\<Sort>(X, a, r)$, $\<Sort>(X, l, b)$.
\endalgo
$\<Sort>(X):$
\algo
+\itemcount=-1
\:Pokud $n=\vert X\vert \le 1$, skonèíme rovnou.
-\:$S\leftarrow\{ (1,n) \}$.
-\:Dokud $S\ne\emptyset$, opakujeme:
-\::Vybereme $(a,b)$ z~$S$.
+\:{\new $S\leftarrow\{ (1,n) \}$.} {\cmt (ná¹ vlastní zásobník)}
+\:{\new Dokud $S\ne\emptyset$, opakujeme:}
+\::{\new Vybereme $(a,b)$ z~$S$.}
\::$m\leftarrow \lfloor (a+b)/2 \rfloor$, $p \leftarrow X[m]$.
\::Pøeházíme prvky \dots\ $\rightarrow l,r$.
-\::Pokud $a<r$, pøidejme $(a,r)$ do~$S$.
-\::Pokud $l<b$, pøidejme $(l,b)$ do~$S$.
+\::{\new Pokud $a<r$, pøidáme $(a,r)$ do~$S$.}
+\::{\new Pokud $l<b$, pøidáme $(l,b)$ do~$S$.}
\endalgo
\endslide
$\<Sort>(X):$
\algo
+\itemcount=-1
\:Pokud $n=\vert X\vert \le 1$, skonèíme rovnou.
-\:$a=1$, $b=n$, $S=\emptyset$.
-\:Opakujeme:
-\::$m\leftarrow \lfloor (a+b)/2 \rfloor$, $p \leftarrow X[m]$.
-\::Pøeházíme prvky \dots\ $\rightarrow l,r$.
-\::Pokud $r-a > b-l$, prohodíme $(a,r) \leftarrow (l,b)$. \\ {\sit (interval $(a,r)$ je teï ten men¹í)}
-\::Pokud $l\ge b$: {\sit (oba intervaly jsou triviální)}
-\:::Pokud $S=\emptyset$, skonèíme.
-\:::Jinak odebereme $(a,b)$ z~$S$.
-\::Jinak: {\sit (vìt¹í je netriviální)}
-\:::Pokud $a\ge r$, pøidej $(a,r)$ do~$S$ {\sit (men¹í také)}
-\:::$(a,b) \leftarrow (l,b)$. {\sit (pokraèujeme vìt¹ím)}
+\:{\new $a\leftarrow 1$, $b\leftarrow n$, $S\leftarrow\emptyset$.}
+\:{\new Opakujeme:} {\cmt (právì tøídíme $X[a],\ldots,X[b]$, $S$ je zásobník)}
+\::Vybereme pivota a pøeházíme prvky \dots\ $\rightarrow l,r$.
+\::{\new Pokud $r-a > b-l$, prohodíme $(a,r) \leftrightarrow (l,b)$. \\ {\cmt (interval $(a,r)$ je teï ten men¹í)}}
+\::{\new Pokud $r>a$:} {\cmt (oba intervaly jsou netriviální)}
+\:::{\new Pøidáme $(l,b)$ do~$S$.} {\cmt (vìt¹í na~zásobník)}
+\:::{\new $(a,b) \leftarrow (a,r)$.} {\cmt (pokraèujeme men¹ím)}
+\::{\new Jinak pokud $b>l$: $(a,b) \leftarrow (l,b)$.} {\cmt (vìt¹í netriviální)}
+\::{\new Jinak:} {\cmt (oba triviální)}
+\:::{\new Pokud $S=\emptyset$, skonèíme.}
+\:::{\new Jinak odebereme $(a,b)$ z~$S$.}
\endalgo
{\sit Nyní staèí $\O(\log n)$ pamìti pro zásobník.}
\endslide
-\slide{Evoluce QuickSortu: Zastavíme se døív}
+\slide{Evoluce QuickSortu: Zkøí¾íme s~InsertSortem}
-$\<Sort>(X):$
+$\<Sort>(X{\new, K}):$ {\cmt ($K$ je vhodná konstanta)}
\algo
-\:Pokud $n=\vert X\vert \le K$, setøídíme InsertSortem.
+\itemcount=-1
+\:{\new Pokud $n=\vert X\vert \le K$, setøídíme InsertSortem.}
\:$a=1$, $b=n$, $S=\emptyset$.
\:Opakujeme:
-\::$m\leftarrow \lfloor (a+b)/2 \rfloor$, $p \leftarrow X[m]$.
-\::Pøeházíme prvky \dots\ $\rightarrow l,r$.
-\::Pokud $r-a > b-l$, prohodíme $(a,r) \leftarrow (l,b)$. \\ {\sit (interval $(a,r)$ je teï ten men¹í)}
-\::Pokud $b-l \le K$: {\sit (oba intervaly jsou malé)}
-\:::Pokud $S=\emptyset$, skonèíme.
-\:::Jinak odebereme $(a,b)$ z~$S$.
-\::Jinak: {\sit (vìt¹í je netriviální)}
-\:::Pokud $r-a > K$, pøidej $(a,r)$ do~$S$ {\sit (men¹í také)}
-\:::$(a,b) \leftarrow (l,b)$. {\sit (pokraèujeme vìt¹ím)}
-\:Dotøídíme posloupnost InsertSortem.
+\::Vybereme pivota a pøeházíme prvky \dots\ $\rightarrow l,r$.
+\::Pokud $r-a > b-l$, prohodíme $(a,r) \leftrightarrow (l,b)$.
+\::{Pokud {\new $r-a > K$}:} {\cmt (oba intervaly jsou netriviální)}
+\:::{Pøidáme $(l,b)$ do~$S$.} {\cmt (vìt¹í na~zásobník)}
+\:::{$(a,b) \leftarrow (a,r)$.} {\cmt (pokraèujeme men¹ím)}
+\::{Jinak pokud {\new $b-l > K$}: $(a,b) \leftarrow (l,b)$.} {\cmt (vìt¹í netriviální)}
+\::{Jinak:} {\cmt (oba triviální)}
+\:::{Pokud $S=\emptyset$, skonèíme.}
+\:::{Jinak odebereme $(a,b)$ z~$S$.}
+\:{\new Dotøídíme posloupnost InsertSortem.} \\ {\cmt (ka¾dý prvek se posune o~nejvý¹e~$K$, tak¾e je to lineární)}
\endalgo
\endslide