slides/quicksort.tex

   1 \input slidemac.tex
   2
   3 \language=\czech
   4 \chyph
   5
   6 \def\cmt{~~\red}
   7
   8 \slide{Evoluce QuickSortu: Pùvodní algoritmus}
   9
  10 $\<Sort>(X):$
  11
  12 \algo
  13 \itemcount=-1
  14 \:Pokud $\vert X \vert \le 1$, vrátíme $X$.
  15 \:Vybereme prostøední prvek~$X$ jako pivota $p$.
  16 \:$M \leftarrow \{ x\in X : x < p \}$, \\
  17   $P \leftarrow \{ x\in X : x = p \}$, \\
  18   $V \leftarrow \{ x\in X : x > p \}$.
  19 \:$M \leftarrow \<Sort>(M)$, \\
  20   $V \leftarrow \<Sort>(V)$.
  21 \:Vrátíme $M+P+V$.
  22 \endalgo
  23
  24 \endslide
  25
  26 \slide{Evoluce QuickSortu: Tøídìní na místì}
  27
  28 $\<Sort>(X, a, b):$
  29
  30 \algo
  31 \itemcount=-1
  32 \:Pokud $a\ge b$, vrátíme se.
  33 \:$m\leftarrow \lfloor (a+b)/2 \rfloor$, $p \leftarrow X[m]$.
  34 \:Pøeházíme prvky tak, aby nalevo byly $\le p$, napravo $\ge p$:
  35 \::$l \leftarrow a$, $r \leftarrow b$.
  36 \::Dokud $l \le r$, opakujeme:
  37 \:::Dokud $X[l]<p$: $l\leftarrow l+1$.
  38 \:::Dokud $X[r]>p$: $r\leftarrow r-1$.
  39 \:::$X[l] \leftrightarrow X[r]$.
  40 \:::$l\leftarrow l+1$, $r\leftarrow r-1$.
  41 \:$\<Sort>(X, a, r)$, $\<Sort>(X, l, b)$.
  42 \endalgo
  43
  44 \endslide
  45
  46 \slide{Evoluce QuickSortu: Zbavíme se rekurze}
  47
  48 $\<Sort>(X):$
  49
  50 \algo
  51 \itemcount=-1
  52 \:Pokud $n=\vert X\vert \le 1$, skonèíme rovnou.
  53 \:{\green $S\leftarrow\{ (1,n) \}$.}
  54 \:{\green Dokud $S\ne\emptyset$, opakujeme:}
  55 \::{\green Vybereme $(a,b)$ z~$S$.}
  56 \::$m\leftarrow \lfloor (a+b)/2 \rfloor$, $p \leftarrow X[m]$.
  57 \::Pøeházíme prvky \dots\ $\rightarrow l,r$.
  58 \::{\green Pokud $a<r$, pøidáme $(a,r)$ do~$S$.}
  59 \::{\green Pokud $l<b$, pøidáme $(l,b)$ do~$S$.}
  60 \endalgo
  61
  62 \endslide
  63
  64 \slide{Evoluce QuickSortu: Omezíme spotøebu pamìti}
  65
  66 $\<Sort>(X):$
  67
  68 \algo
  69 \itemcount=-1
  70 \:Pokud $n=\vert X\vert \le 1$, skonèíme rovnou.
  71 \:{\green $a\leftarrow 1$, $b\leftarrow n$, $S\leftarrow\emptyset$.}
  72 \:{\green Opakujeme:}
  73 \::$m\leftarrow \lfloor (a+b)/2 \rfloor$, $p \leftarrow X[m]$.
  74 \::Pøeházíme prvky \dots\ $\rightarrow l,r$.
  75 \::{\green Pokud $r-a > b-l$, prohodíme $(a,r) \leftarrow (l,b)$. \\ {\cmt (interval $(a,r)$ je teï ten men¹í)}}
  76 \::{\green Pokud $l\ge b$: {\cmt (oba intervaly jsou triviální)}}
  77 \:::{\green Pokud $S=\emptyset$, skonèíme.}
  78 \:::{\green Jinak odebereme $(a,b)$ z~$S$.}
  79 \::{\green Jinak: {\cmt (vìt¹í je netriviální)}}
  80 \:::{\green Pokud $a\ge r$, pøidáme $(a,r)$ do~$S$ {\cmt (men¹í také)}}
  81 \:::{\green $(a,b) \leftarrow (l,b)$. {\cmt (pokraèujeme vìt¹ím)}}
  82 \endalgo
  83
  84 {\sit Nyní staèí $\O(\log n)$ pamìti pro zásobník.}
  85
  86 \endslide
  87
  88 \slide{Evoluce QuickSortu: Zkøí¾íme s~InsertSortem}
  89
  90 $\<Sort>(X):$
  91
  92 \algo
  93 \itemcount=-1
  94 \:{\green Pokud $n=\vert X\vert \le K$, setøídíme InsertSortem.}
  95 \:$a=1$, $b=n$, $S=\emptyset$.
  96 \:Opakujeme:
  97 \::$m\leftarrow \lfloor (a+b)/2 \rfloor$, $p \leftarrow X[m]$.
  98 \::Pøeházíme prvky \dots\ $\rightarrow l,r$.
  99 \::Pokud $r-a > b-l$, prohodíme $(a,r) \leftarrow (l,b)$. \\ {\cmt (interval $(a,r)$ je teï ten men¹í)}
 100 \::{\green Pokud $b-l \le K$: {\cmt (oba intervaly jsou triviální)}}
 101 \:::Pokud $S=\emptyset$, skonèíme.
 102 \:::Jinak odebereme $(a,b)$ z~$S$.
 103 \::Jinak: {\cmt (vìt¹í je netriviální)}
 104 \:::{\green Pokud $r-a > K$, pøidej $(a,r)$ do~$S$ {\cmt (men¹í také)}}
 105 \:::$(a,b) \leftarrow (l,b)$. {\cmt (pokraèujeme vìt¹ím)}
 106 \:{\green Dotøídíme posloupnost InsertSortem.}
 107 \endalgo
 108
 109 \endslide
 110
 111 \end