Třídění

BubbleSort

Je to třídící algoritmus třídící v čase $O(n^2)$, pro každý s $n$ prvků musíme udělat až $n$ porovnání.

$$\begin{array}{rl}& \text{BubbleSort}\\ & \text{Vstup: Pole }P[1,\dots ,n]\\ & \text{Vyˊstup: Setrˇıˊzeneˊ pole }P\\ & \text{1. }pokra\check{c}uj\leftarrow 1\\ & \text{2. Dokud je }pokra\check{c}uj=1:\\ & \text{3. }pokra\check{c}uj\leftarrow 0\\ & \text{4. }\text{Pro }i=1,2,\dots ,n-1:\\ & \text{5. }\text{Pokud }P[i]>P[i+1]:\\ & \text{6. }\text{Prohodıˊme }P[i]\text{ a }P[i+1]\text{.}\\ & \text{7. }pokra\check{c}uj\leftarrow 1\end{array}$$

---

InsertionSort

Je to třídící algoritmus s časovou složitostí $O(n^2)$ v nejhorším případě. V každém kroku vkládáme prvek na správné místo mezi již setříděné prvky.

$$\begin{array}{rl}& \text{InsertionSort}\\ & \text{Vstup: Pole }P[1,\dots ,n]\\ & \text{Vyˊstup: Setrˇıˊzeneˊ pole }P\\ & \text{1. Pro }i=2,3,\dots ,n:\\ & \text{2. }\text{klıˊcˇ }\leftarrow P[i]\\ & \text{3. }j\leftarrow i-1\\ & \text{4. }\text{Dokud }j\ge 1\text{ a }P[j]>\text{klıˊcˇ}:\\ & \text{5. }P[j+1]\leftarrow P[j]\\ & \text{6. }j\leftarrow j-1\\ & \text{7. }P[j+1]\leftarrow \text{klıˊcˇ}\end{array}$$

---

QuickSort

$$\begin{array}{rl}& \text{QuickSort}\\ & \text{Vstup: Posloupnost }X=x_1,\dots ,x_n\\ & \text{Vyˊstup: Setrˇıˊzenaˊ posloupnost }Y\\ & \text{1. Pokud }n\le 1,\text{vraˊtıˊme }Y=X\text{ a skoncˇıˊme.}\\ & \text{2. }p\leftarrow \text{neˇkteryˊ z prvku˚ }{x}_1,\dots ,x_n\text{ jako pivot.}\\ & \text{3. }L\leftarrow \text{ prvky }X\text{ jenzˇ jsou mensˇıˊ nezˇ }p\\ & \text{4. }P\leftarrow \text{ prvky }X\text{ jenzˇ jsou veˇtsˇıˊ nezˇ }p\\ & \text{5. }S\leftarrow \text{ prvky }X\text{ jenzˇ jsou rovny }p\\ & \text{6. }L\leftarrow \text{QuickSort}(L)\\ & \text{7. }R\leftarrow \text{QuickSort}(R)\\ & \text{8. }\text{Vraˊtıˊme }Y\leftarrow L.S.R\end{array}$$

Algoritmus v každé vrstvě stráví $n$ času a vrstev je $O(\log n)$ protože zvolením pivota jako “skoromediánu” máme dělení na podobné části. tedy složitost je $O(n\cdot \log n)$.

---

Dolní odhad složitosti porovnávacích třídicích algoritmů

---

Každý porovnávací třídicí algoritmus má v nejhorším případě časovou složitost alespoň:

$$\boxed{\Omega (n\log n)}$$

Porovnávací třídicí algoritmus lze modelovat jako rozhodovací strom, kde:

• Každý vnitřní uzel představuje porovnání dvou prvků.
• Každá hrana odpovídá výsledku porovnání (např. „menší“ nebo „větší“).
• Každý list odpovídá jedné možné výstupní permutaci.

Aby algoritmus mohl správně roztřídit všech $n$ vstupních prvků ve všech případech, musí být strom schopen reprezentovat všechna jejich uspořádání.

Krok 1: Počet možných výstupů

• Všechny možné permutace $n$ různých prvků: $n!$
• Tedy rozhodovací strom musí mít alespoň $n!$ listů.

Krok 2: Výška binárního stromu

• Binární strom s výškou $h$ má nejvýše $2^h$ listů.
• Musí tedy platit: $2^h\ge n!$
• ⇒ ${\log }_2(n!)\le h$

Krok 3: Stirlingova aproximace

$$n!\ge {\left(\frac{n}{e}\right)}^n$$

Zlogaritmujeme:

$${\log }_2(n!)\ge {\log }_2\left({\left(\frac{n}{e}\right)}^n\right)=n{\log }_2\left(\frac{n}{e}\right)=n{\log }_{2}n-n{\log }_{2}e$$

Tedy:

$${\log }_2(n!)=\Omega (n\log n)$$