slides/quicksort.tex

   1 \input slidemac.tex
   2
   3 \language=\czech
   4 \chyph
   5
   6 \def\new{\color{Blue}}
   7 \def\cmt{~~\color{RawSienna}}
   8
   9 \slide{Evoluce QuickSortu: Pùvodní algoritmus}
  10
  11 $\<Sort>(X):$
  12
  13 \algo
  14 \itemcount=-1
  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)$.
  22 \:Vrátíme $M+P+V$.
  23 \endalgo
  24
  25 \bigskip
  26
  27 {\sit Èas: $\O(n\log n)$ prùmìrnì}
  28
  29 {\sit Pamì»: $\O(n)$ na~pomocná pole, $\O(n)$ na zásobník}
  30
  31 \endslide
  32
  33 \slide{Evoluce QuickSortu: Tøídìní na místì}
  34
  35 $\<Sort>(X, a, b):$ {\cmt (setøídí prvky $X[a],\ldots,X[b]$)}
  36
  37 \algo
  38 \itemcount=-1
  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$.
  46 \:::$X[l] \leftrightarrow X[r]$.
  47 \:::$l\leftarrow l+1$, $r\leftarrow r-1$.
  48 \:$\<Sort>(X, a, r)$, $\<Sort>(X, l, b)$.
  49 \endalgo
  50
  51 \endslide
  52
  53 \slide{Evoluce QuickSortu: Zbavíme se rekurze}
  54
  55 $\<Sort>(X):$
  56
  57 \algo
  58 \itemcount=-1
  59 \:Pokud $n=\vert X\vert \le 1$, skonèíme rovnou.
  60 \:{\new $S\leftarrow\{ (1,n) \}$.} {\cmt (ná¹ vlastní zásobník)}
  61 \:{\new Dokud $S\ne\emptyset$, opakujeme:}
  62 \::{\new Vybereme $(a,b)$ z~$S$.}
  63 \::$m\leftarrow \lfloor (a+b)/2 \rfloor$, $p \leftarrow X[m]$.
  64 \::Pøeházíme prvky \dots\ $\rightarrow l,r$.
  65 \::{\new Pokud $a<r$, pøidáme $(a,r)$ do~$S$.}
  66 \::{\new Pokud $l<b$, pøidáme $(l,b)$ do~$S$.}
  67 \endalgo
  68
  69 \endslide
  70
  71 \slide{Evoluce QuickSortu: Omezíme spotøebu pamìti}
  72
  73 $\<Sort>(X):$
  74
  75 \algo
  76 \itemcount=-1
  77 \:Pokud $n=\vert X\vert \le 1$, skonèíme rovnou.
  78 \:{\new $a\leftarrow 1$, $b\leftarrow n$, $S\leftarrow\emptyset$.}
  79 \:{\new Opakujeme:} {\cmt (právì tøídíme $X[a],\ldots,X[b]$, $S$ je zásobník)}
  80 \::Vybereme pivota a pøeházíme prvky \dots\ $\rightarrow l,r$.
  81 \::{\new Pokud $r-a > b-l$, prohodíme $(a,r) \leftrightarrow (l,b)$. \\ {\cmt (interval $(a,r)$ je teï ten men¹í)}}
  82 \::{\new Pokud $r>a$:} {\cmt (oba intervaly jsou netriviální)}
  83 \:::{\new Pøidáme $(l,b)$ do~$S$.} {\cmt (vìt¹í na~zásobník)}
  84 \:::{\new $(a,b) \leftarrow (a,r)$.} {\cmt (pokraèujeme men¹ím)}
  85 \::{\new Jinak pokud $b>l$: $(a,b) \leftarrow (l,b)$.} {\cmt (vìt¹í netriviální)}
  86 \::{\new Jinak:} {\cmt (oba triviální)}
  87 \:::{\new Pokud $S=\emptyset$, skonèíme.}
  88 \:::{\new Jinak odebereme $(a,b)$ z~$S$.}
  89 \endalgo
  90
  91 {\sit Nyní staèí $\O(\log n)$ pamìti pro zásobník.}
  92
  93 \endslide
  94
  95 \slide{Evoluce QuickSortu: Zkøí¾íme s~InsertSortem}
  96
  97 $\<Sort>(X{\new, K}):$ {\cmt ($K$ je vhodná konstanta)}
  98
  99 \algo
 100 \itemcount=-1
 101 \:{\new Pokud $n=\vert X\vert \le K$, setøídíme InsertSortem.}
 102 \:$a=1$, $b=n$, $S=\emptyset$.
 103 \:Opakujeme:
 104 \::Vybereme pivota a pøeházíme prvky \dots\ $\rightarrow l,r$.
 105 \::Pokud $r-a > b-l$, prohodíme $(a,r) \leftrightarrow (l,b)$.
 106 \::{Pokud {\new $r-a > K$}:} {\cmt (oba intervaly jsou netriviální)}
 107 \:::{Pøidáme $(l,b)$ do~$S$.} {\cmt (vìt¹í na~zásobník)}
 108 \:::{$(a,b) \leftarrow (a,r)$.} {\cmt (pokraèujeme men¹ím)}
 109 \::{Jinak pokud {\new $b-l > K$}: $(a,b) \leftarrow (l,b)$.} {\cmt (vìt¹í netriviální)}
 110 \::{Jinak:} {\cmt (oba triviální)}
 111 \:::{Pokud $S=\emptyset$, skonèíme.}
 112 \:::{Jinak odebereme $(a,b)$ z~$S$.}
 113 \:{\new Dotøídíme posloupnost InsertSortem.} \\ {\cmt (ka¾dý prvek se posune o~nejvý¹e~$K$, tak¾e je to lineární)}
 114 \endalgo
 115
 116 \endslide
 117
 118 \end