5-qs/5-qs.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{3}{Tøídìní}{(N.O.Body)}
   4
   5 Dostaneme posloupnost, její¾ prvky dovedeme porovnávat, a sna¾íme se co
   6 nejefektivnìji posloupnost setøídit. Mù¾eme napøíklad pou¾ít metodu Rozdìl a panuj:
   7
   8 \s{Algoritmus:} (QuickSort)
   9
  10 \def\concat{\mathop{\hbox{.}}}
  11
  12 \algo
  13 \:Pokud $\vert X\vert \leq 1$, vrátíme~$X$.
  14 \:Vybereme pivota $p \in X$ (pozdìji upøesníme, jak).
  15 \:$M = \{x \in X ; x \le p\}$
  16 \:$P = \{x \in X ; x = p\}$
  17 \:$V = \{x \in X ; x \ge p\}$
  18 \:Vrátíme $\<Quicksort>(M) \concat P \concat \<Quicksort>(V)$ \foot{Operátor \uv{$\concat$} znaèí zøetìzení seznamù}
  19 \endalgo
  20
  21 \s{Pozorování:}
  22 \itemize\ibull
  23 \:zastaví se
  24 \:vydá správný výsledek (dùkaz napø. indukcí podle $\vert X\vert$)
  25 \:pivot
  26   \itemize\istar
  27   \:pøi ideální volbì: $$ T(n) = 2T(n/2) + O(n) = O(n\log n) $$ (jako u mergesortu)
  28   \:pøi ¹patné volbì: $$ T(n) = T(n - 1) + \Theta(n) = \Theta(n^2) $$
  29   \endlist
  30 \:chová se v prùmìru dobøe, a¾ na multiplikativní konstantu
  31 \endlist
  32
  33     \s{Vìta:} QS s náhodnou volbou pivota má slo¾itost prùmìrnì $\O(n\log n)$
  34 \foot{Vìta': QS s pevnou volbou pivota má v prùmìru pøes v¹echny permutace na vstupu èasovou slo¾itost $\O(n\log n)$.}
  35
  36 \bye