\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)$.}

\proof

\figure{strom-dukaz.eps}{Dùkaz rozdìlením na fáze}{0.3\hsize}

Provedeme rozdìlováním na fáze, pøi¾em¾ fází rozumíme cestu ve stromu, která sleduje
vìt¹í díl a konèí, kdy¾ se povede vybrat za pivota l¾imedián.
\qed

\s{Pozorování:}

\itemize\ibull
\:Ka¾dá fáze rozdìlí vstup na disjunktní èásti a pivoty $X_1, \ldots, X_k$ ($k \geq 2$)

\:$\forall i: \vert X_i \vert \leq {3\over 4} \vert X \vert$

\:$\sum_i  \vert X_i \vert \leq \vert X \vert$

\:prùmìrná délka fáze je nejvý¹e~2 (proto¾e pravdìpodobnost na vybrání l¾imediánu je alespoò $1/2$)

\:v prùmìru poèítáme jednu fázi v èase $\O(n)$

\:Proto $T(n) = \sum_i T (n_i) + \O(n)$, kde $n = \vert X \vert$, $n_i = \vert X_i \vert$.

\endlist

\s{Komprimovaný strom}

<!-- obrázek -->

Hloubka je logaritmická $\Rightarrow$ $\O(log n)$ (proto¾e velikost
fáze klesá exponencálnì, a tak po $\O(\log n)$ krocích dostaneme posloupnosti
velikosti~1).

Práce na jedné hladinì je $\O(n)$.

$\Downarrow$

Celková èasová slo¾itost je tedy v~prùmìru $\O(n \log n)$.

Pamì»ové nároky jsou:
$\O(n)$ na pomocné pole
$\O(n)$ na zásobníku


Dal¹í modifikace QSortu mù¾ete najít na: 
http://mj.ucw.cz/vyuka/0607/ads1/quicksort.pdf


\s{Vìta:}
Ka¾dý tøídící algoritmus zalo¾ený na porovnávání
(a prohazování) potøebuje na~vstup délky~$n$ v~nejhor¹ím pøípadì
$\Omega (n \log n)$ porovnání.

\proof
\itemize\ibull
  \:BÚNO nejdøíve algoritmus porovnává a potom
  prohazuje (algoritmus mù¾eme upravit tak aby
  prohazoval a¾ na~konci).

  \:BÚNO hledáme vstupy, které jsou permutace na $\{1 - n\}$.

  \:Sestrojíme rozhodovací strom na¹eho algoritmu

<!-- obrázek -->

  \:Je vidìt, ¾e existence dvou rùzných $\Pi_1$ a $\Pi_2 $,
  pøi kterých bychom skonèili ve stejném listu vede ke sporu, 
  pøitom poèet listù $\geq n!$
\endlist

{\narrower
  \s{Pozorování:} Binární strom hloubku $k$ má poèet listù $\leq 2^k$.
  Uva¾me binární strom hloubky $k$ s maximálním poètem listù, pak v¹echny listy
  le¾í na poslední hladinì. Víme, ¾e na $i$-té hladinì je $2^i$ vrcholù a
  poèet listù je $2^k$. Odtud plyne, ¾e v ka¾édém binárním stromu je maximálnì $2^k$ listù

}

  pokraèování pùvodního dùkazu...

  Z toho co u¾ víme plyne, ¾e hloubka stromu je nejvý¹e $\log(n!)$.

  Z diskrétní matematiky víme ¾e: \
  ${n^{n / 2} \leq n!} \leq (n / 2)^n$
  
  My potøebujeme jen levou èást, tedy ¾e ${n^{n / 2} \leq n!}$
  Toto jde dokázat pou¾ítím "AG Nerovnosti" 
  
  ...tedy dostáváme, ¾e hloubka stromu je $\geq \log (n^{n / 2}) = (n / 2)
  \log (n) \Longrightarrow \Omega (n \log n)$

\qed

\bye
