\input slidemac.tex

\language=\czech
\chyph

\slide{Evoluce QuickSortu: Pùvodní algoritmus}

$\<Sort>(X):$

\algo
\:Pokud $\vert X \vert \le 1$, vrátíme $X$.
\:Vybereme prostøední prvek~$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 \}$.
\:$M \leftarrow \<Sort>(M)$, \\
  $V \leftarrow \<Sort>(V)$.
\:Vrátíme $M+P+V$.
\endalgo

\endslide

\slide{Evoluce QuickSortu: Tøídìní na místì}

$\<Sort>(X, a, b):$

\algo
\:Pokud $a\ge b$, vrátíme se.
\:$m\leftarrow \lfloor (a+b)/2 \rfloor$, $p \leftarrow X[m]$.
\: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$.
\:$\<Sort>(X, a, r)$, $\<Sort>(X, l, b)$.
\endalgo

\endslide

\slide{Evoluce QuickSortu: Zbavíme se rekurze}

$\<Sort>(X):$

\algo
\:Pokud $n=\vert X\vert \le 1$, skonèíme rovnou.
\:$S\leftarrow\{ (1,n) \}$.
\:Dokud $S\ne\emptyset$, opakujeme:
\::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$.
\endalgo

\endslide

\slide{Evoluce QuickSortu: Omezíme spotøebu pamìti}

$\<Sort>(X):$

\algo
\: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)}
\endalgo

{\sit Nyní staèí $\O(\log n)$ pamìti pro zásobník.}

\endslide

\slide{Evoluce QuickSortu: Zastavíme se døív}

$\<Sort>(X):$

\algo
\: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.
\endalgo

\endslide

\end
