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 \:::Je-li $l\le r$:
  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)$.
  51 \endalgo
  52
  53 \endslide
  54
  55 \slide{Evoluce QuickSortu: Zbavíme se rekurze}
  56
  57 $\<Sort>(X):$
  58
  59 \algo
  60 \itemcount=-1
  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$.}
  69 \endalgo
  70
  71 \endslide
  72
  73 \slide{Evoluce QuickSortu: Omezíme spotøebu pamìti}
  74
  75 $\<Sort>(X):$
  76
  77 \algo
  78 \itemcount=-1
  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$.}
  91 \endalgo
  92
  93 {\sit Nyní staèí $\O(\log n)$ pamìti pro zásobník.}
  94
  95 \endslide
  96
  97 \slide{Evoluce QuickSortu: Zkøí¾íme s~InsertSortem}
  98
  99 $\<Sort>(X{\new, K}):$ {\cmt ($K$ je vhodná konstanta)}
 100
 101 \algo
 102 \itemcount=-1
 103 \:{\new Pokud $n=\vert X\vert \le K$, setøídíme InsertSortem.}
 104 \:$a=1$, $b=n$, $S=\emptyset$.
 105 \:Opakujeme:
 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í)}
 116 \endalgo
 117
 118 \endslide
 119
 120 \end