From bd84c3da400398332700082e36f48d673630b393 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Mon, 14 May 2007 19:46:10 +0200
Subject: [PATCH] Prvnich par odstavcu pate prednasky.

---
 5-qs/5-qs.tex | 36 ++++++++++++++++++++++++++++++++++++
 5-qs/Makefile |  3 +++
 2 files changed, 39 insertions(+)
 create mode 100644 5-qs/5-qs.tex
 create mode 100644 5-qs/Makefile

diff --git a/5-qs/5-qs.tex b/5-qs/5-qs.tex
new file mode 100644
index 0000000..b95ea4f
--- /dev/null
+++ b/5-qs/5-qs.tex
@@ -0,0 +1,36 @@
+\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
diff --git a/5-qs/Makefile b/5-qs/Makefile
new file mode 100644
index 0000000..c3461da
--- /dev/null
+++ b/5-qs/Makefile
@@ -0,0 +1,3 @@
+P=5-qs
+
+include ../Makerules
-- 
2.39.2