\input ../lecnotes.tex

\prednaska{5}{QuickSort a slo¾itost tøídìní}{(Michal Sta¹a, ???)}

Dostaneme posloupnost, její¾ prvky dovedeme porovnávat, a sna¾íme se co
nejefektivnìji posloupnost setøídit. Uká¾eme si tøídící algoritmus QuickSort
(pro pøátele QS) zalo¾ený na metodì 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$.\foot{pozdìji upøesníme, jak}
\:$M \leftarrow \{x \in X ; x \le p\}$.
\:$P \leftarrow \{x \in X ; x = p\}$.
\:$V \leftarrow \{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{Rozbor:}
V¹imnìme si, ¾e QS se urèitì zastaví a také ¾e vydá
správný výsledek. To mù¾eme ovìøit napø. indukcí podle $\vert X\vert$.

Podobnì jako u~vybírání $k$-tého nejmen¹ího prvku v~minulých pøedná¹kách
i zde èasová slo¾itost závisí hlavnì na~volbì pivota. Kdybychom za~pivota
zvolili medián, vy¹la by èasová slo¾itost stejnì jako u~MergeSortu:
  $$ T(n) = 2T(n/2) + O(n) = O(n\log n). $$
Pokud naopak budeme volit pivota ne¹ikovnì, dostaneme:
  $$ T(n) = T(n - 1) + \Theta(n) = \Theta(n^2). $$
V ideálním pøípadì bychom tedy chtìli za pivota zvolit medián, av¹ak jeho pøímým výpoètem
bychom algoritmus pøíli¹ zpomalili.
Pou¾ívá se proto mnoho zpùsobù, jak vybrat rychle pivota blízkého mediánu.
Èasto pou¾ívanou metodou je náhodný výbìr, v~praxi realizovaný nìjakým pseudonáhodným
generátorem. Uká¾eme, ¾e v~tomto pøípadì je QS v~prùmìrném pøípadì rychlý:

\s{Vìta:} QS s~náhodnou volbou pivota má èasovou slo¾itost v~prùmìru
$\O(n\log n)$.

\s{Poznámka:} Stejnì jako u~výbìru $k$-tého nejmen¹ího prvku bychom také
mohli ukázat, ¾e QS s~pevnou volbou pivota spu¹tìný na~náhodnou permutaci
má tuté¾ èasovou slo¾itost. Detaily nicménì vynecháme.

\noindent {\sl Dùkaz vìty:}

Rozdìlíme bìh algoritmu na~fáze, pøièem¾ fází rozumíme cestu ve~stromu volání,
která sleduje vìt¹í díl a konèí, kdy¾ se povede vybrat za pivota l¾imedián.

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

Ka¾dá fáze pøitom rozdìlí vstup na~disjunktní èásti $X_1, \ldots, X_k$ ($k\ge 2$)
a pivoty, kteøí je oddìlují. Proto je $\sum_i n_i \leq n$,
kde $n$ znaèí velikost vstupu a~$n_i$ velikost $i$-té èásti. Velikost ka¾dé
èásti je navíc nejvý¹e $3/4 \cdot n$ (na~konci fáze to platí proto, ¾e jsme
zvolili l¾imedián, pøedtím jsme v¾dy oddìlili men¹í z~èástí, èili nejvý¹e $n/2$).

Jedna iterace algoritmu trvá~$\O(n)$ a jeliko¾ l¾imedián vybereme s~pravdìpodobností alespoò $1/2$,
je v~jedné fázi v~prùmìru $\O(1)$ iterací a celá fáze proto v~prùmìru trvá èas~$\O(n)$.
Z~toho dostaneme následující rekurenci pro prùmìrnou èasovou slo¾itost celého algoritmu:
$${\bb E}T(n) = \sum_i {\bb E}T (n_i) + \O(n).$$

Tento typ rekurence jsme je¹tì nepotkali a Kuchaøková vìta na~ni nezabere,
ov¹em mù¾eme si pomoci jednoduchou úvahou. Pøedstavme si, ¾e v~na¹em stromu
rekurzivních volání zkomprimujeme ka¾dou fázi do~jednoho vrcholu. Tím vznikne
strom, který odpovídá algoritmu, jen¾ v~jedné iteraci v~prùmìrnì lineárním
èase rozdìlí vstup na~nìkolik èástí a rekurzivnì se na~nì zavolá.

\s{FIXME:} Obrázek

Nový strom má logaritmickou hloubku, proto¾e na~ka¾dé dal¹í hladinì jsou
délky posloupností nejvý¹e $3/4$ délek z~pøedchozí hladiny. Navíc souèet
délek pøes ka¾dou hladinu je maximálnì~$n$. Proto na~ka¾dé hladinì
trávíme èas v~prùmìru $\O(n)$ a v~celém stromu tedy $\O(n\log n)$.
\qed

\s{Pozorování:} Na¹e první verze QS spotøebuje lineární mno¾ství pamìti
na~pomocné pole a na~zásobník. Na~pøedná¹ce jsme ukazovali rùzná jeho
praktická vylep¹ení, které staèí pomocná pamì» o~velikosti $\O(\log n)$.
Detaily viz webové stránky pøedná¹ky.

Známe u¾ nìkolik tøídících algoritmù s~èasovou slo¾itostí $\O(n\log n)$.
Následující vìta ukazuje, ¾e efektivnìj¹í algoritmus v~obecném pøípadì
nese¾eneme.

\s{Vìta:}
Ka¾dý tøídící algoritmus zalo¾ený na porovnávání a prohazování prvkù
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 si pamatoval
  aktuální permutaci prvkù a podle ní prohazoval a¾ na~konci).

  \:BÚNO je vstup algoritmu permutace na~mno¾inì $\{1, \ldots, n\}$.

  \:Chování algoritmu popí¹eme rozhodovacím stromem. Jeho vnitøní vrcholy
    urèují jednotlivá porovnání prvkù, listy odpovídají okam¾ikùm, kdy
    algoritmus pøestal porovnávat a zaèal prohazovat.

\s{FIXME: Obrázek}

  \:V¹imneme si, ¾e nemohou existovat dvì vstupní permutace, pro které
    by algoritmus skonèil v~tém¾e listu rozhodovacího stromu, jeliko¾
    v~okam¾iku, kdy algoritmus dorazí do~listu, nemù¾e u¾ získávat
    ¾ádné informace o~vstupu a ¾ádná posloupnost prohození nemù¾e
    setøídit jak první, tak druhou permutaci. Listù stromu je tedy
    alespoò tolik, kolik je rùzných vstupù, tedy~$n!$.

{\parindent=\leftskip\narrower
  \s{Lemmátko:} Binární strom hloubky~$k$ má nejvý¹e $\leq 2^k$ listù.
  \par\noindent {\sl Dùkazík:} Uva¾me binární strom hloubky $k$ s~maximálním poètem
  listù. V~takovém stromu budou v¹echny listy urèitì le¾et na~poslední hladinì
  (kdyby nele¾ely, mù¾eme pod nìkterý list na~vy¹¹í hladinì pøidat dal¹í dva vrcholy a získat
  tak \uv{listnatìj¹í} strom stejné hloubky). Jeliko¾ na~$i$-té hladinì je nejvý¹e $2^i$
  vrcholù, v¹ech listù je nejvý¹e~$2^k$.
  \qed

}

  Z~tohoto lemmátka plyne, ¾e rozhodovací strom musí být hluboký alespoò
  $\log n!$.

  \:Zbytek je u¾ snadné cvièení z~diskrétní matematiky:

{\parindent=\leftskip\narrower
  \s{Lemmátko:} $ n! \ge n^{n / 2} $.
  \par\noindent {\sl Dùkazík:} $n! = \sqrt{(n!)^2} = \sqrt{1(n-1)\cdot 2(n-2) \cdot \ldots \cdot n\cdot 1}$,
  co¾ mù¾eme také zapsat jako $\sqrt{1(n-1)}\cdot \sqrt{2(n-2)} \cdot \ldots \cdot \sqrt{n\cdot 1}$.
  Pøitom pro ka¾dé $1\le k\le n$ je $k(n+1-k) = kn + k - k^2 = n + (k-1)n + k(1-k) = n + (k-1)(n-k) \ge n$.
  Proto je ka¾dá z~odmocnin vìt¹í nebo rovna $n^{1/2}$ a $n!\ge (n^{1/2})^n = n^{n/2}$.
  \qed

}

  Hloubka stromu tedy èiní minimálnì $\log n! \ge \log(n^{n/2}) = n/2 \cdot \log n = \Omega(n\log n)$,
  co¾ také zdola odhaduje poèet porovnání, který algoritmus provede v~nejhor¹ím pøípadì.
\qed

\bye
