Problém třídění, rozdělení třídících algoritmů, dolní mez složitosti třídění porovnáváním

Název: Problém třídění
Vstup: Posloupnost $n$ čísel $< a_{1}, ..., a_{n} >$
Výstup: Permutace $< b_{1}, ..., b_{n} >$ vstupní posloupnosti taková, že $b_{1} \leq b_{2} \leq ... \leq b_{n}$
Proč je problém třídění důležitý:
- Vyskytuje se jako úloha při řešení mnoha úloh zpracování dat.
- Algoritmy pro řešení složitějších problémů využívají algoritmy pro třídění.
- Často potřebujeme setřídit pole složitějších datových položek než jsou čísla.
- Algoritmy třídění používají řadu užitečných technik pro návrh algoritmů.

Podle způsobu třídění:
- Porovnávací algoritmy:
  - Tyto algoritmy porovnávají prvky, aby je mohli správně seřadit
  - Quicksort, Mergesort, Heapsort, …
- Některé třídící algoritmy, například Counting Sort nebo Radix Sort nepoužívají porovnání prvků, ale pracují s počtem výskytů nebo s číslicemi v číslech.
Podle časové složitosti:
- Algoritmy s časovou složitostí $O (n^{2})$
  - Bubble Sort, Selection Sort, Insertion Sort.
- Algoritmy s časovou složitostí $O (n lo g n)$
  - QuickSort, MergeSort, HeapSort.
- Lineární algoritmy s časovou složitostí $O (n)$
  - Counting Sort, Radix Sort.
Podle stability:
- Stabilní algoritmy
  - Zachovávají pořadí stejných prvků v seznamu
  - MergeSort, Insertion Sort.
- Nestabilní algoritmy
  - Mohou zaměnit pořadí stejných prvků
  - QuickSort, Selection Sort
Podle paměťové náročnosti:
- In-place algoritmy
  - Provádějí třídění přímo v původním seznamu a nepotřebují žádnou další paměťovou alokaci.
  - QuickSort, Selection Sort.
- Out-of-place algoritmy
  - Vytvářejí nový seznam pro seřazené prvky a mohou potřebovat více paměti.
  - MergeSort, Counting Sort.

Věta: Časová složitost v nejhorším případě libovolného algoritmu třídění porovnáváním je $Ω (n l g n)$ .

Důkaz

Zkoušky