\input ../lecnotes.tex

\prednaska{3}{Tøídìní}{(N.O.Body)}

Dostaneme posloupnost, její¾ prvky dovedeme porovnávat, a sna¾íme se co
nejefektivnìji posloupnost setøídit. Mù¾eme napøíklad pou¾ít metodu Rozdìl a panuj:

\s{Algoritmus:} (QuickSort)

\def\concat{\mathop{\hbox{.}}}

\algo
\:Pokud $\vert X\vert \leq 1$, vrátíme~$X$.
\:Vybereme pivota $p \in X$ (pozdìji upøesníme, jak).
\:$M = \{x \in X ; x \le p\}$
\:$P = \{x \in X ; x = p\}$
\:$V = \{x \in X ; x \ge p\}$
\:Vrátíme $\<Quicksort>(M) \concat P \concat \<Quicksort>(V)$ \foot{Operátor \uv{$\concat$} znaèí zøetìzení seznamù}
\endalgo

\s{Pozorování:}
\itemize\ibull
\:zastaví se
\:vydá správný výsledek (dùkaz napø. indukcí podle $\vert X\vert$)
\:pivot
  \itemize\istar
  \:pøi ideální volbì: $$ T(n) = 2T(n/2) + O(n) = O(n\log n) $$ (jako u mergesortu)
  \:pøi ¹patné volbì: $$ T(n) = T(n - 1) + \Theta(n) = \Theta(n^2) $$
  \endlist
\:chová se v prùmìru dobøe, a¾ na multiplikativní konstantu
\endlist

    \s{Vìta:} QS s náhodnou volbou pivota má slo¾itost prùmìrnì $\O(n\log n)$
\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)$.}

\bye
