slides/quicksort.tex

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