Třídící algoritmy

Paměťová náročnost

Algoritmus třídí prvky na místě (in place), pokud prvky neopouštějí paměťové buňky, v nichž byly zadány, s možnou výjimkou konstantně mnoha tzv. pracovních buněk. Kromě toho může algoritmus ukládat libovolné množství číselných proměnných (indexy prvků, parametry funkcí apod.), které prohlásíme za pomocnou paměť algoritmu.

Offline/Online algoritmus

Offline: Nejdřív přijme všechny úkoly a pak je zpracuje najednouv pořadí priorit. To vyžaduje vzestupné seřazení úkolů podle priorit.

Online: Úkoly chodí průběžně během zpracovávání předchozích.

Stabilní algoritmus

Algoritmus je stabilní, pokud kdykoliv si prvky p_i a p_j rovny, tak jejich vzájemné pořadí na výstupu se shoduje s jejich pořadím na vstupu. Tedy pokud je p_i = p_j pro i < j, pak se p_i ve vstupu objeví před p_j.

Inkrementální

Dodejme ještě, že úvaha typu „jak se změní výstup, když na konec vstupu přidáme další prvek?“ je poměrně častá. Vysloužila si proto zvláštní jméno, algoritmům tohoto druhu se říká inkrementální. Ještě se s nimi několikrát potkáme.

Další vlastnosti

• Základní operace:
  • Řazení založené na pouze binární operaci porovnání-a-prohození (Compare-And-Exchange).
  • Řazení založené na jiné operaci.
• Citlivost na hodnoty prvků vstupní posloupnosti:
  • Datově citlivé algoritmy.
  • Datově necitlivé algoritmy.

Porovnávací model

Každý deterministický algoritmus v porovnávacím modelu, který nalezne zadaný prvek v n-prvkové seřazené posloupnosti, použije v nejhorším případě Ω(log n) porovnání.

Obecně problémy třídění prvku mají Ω(n.log(n)) složitost. To znamená, že existuje algoritmus schopný seřadit n prvků v čase O(n log n) a zároveň neexistuje asymptoticky rychlejší algoritmus. Dokážeme, že v porovnávacím modelu nemůže rychlejší třídicí algoritmus existovat.

Problém řazení v porovnávacím modelu

1. Vstupem algoritmu je posloupnost n prvků a₁, … , a_n konstantní velikosti.

2. Stroj má funkci komparátor - která pro libovolné dva prvky a_i a a_j vrátí zda:

   • a_i < a_j
   • a_i > a_j
   • a_i = a_j

3. Úkolem algoritmu je přerovnat (permutovat) prvky v paměti do nějakého pořadí b₁ ≤ b₂ ≤ … ≤ b_n.

4. Algoritmus smí prvky pouze vzájemně porovnávat a přesouvat v paměti.

Možné průběhy výpočtu tedy můžeme popsat takzvaným rozhodovacím stromem. V každém vnitřním vrcholu tohoto stromu je jedno porovnání typu x ≤ ai. Vrchol má tři potomky, kteří odpovídají možným výsledkům tohoto porovnání (menší, větší, rovno). Může se stát, že některé z výsledků nemohou nastat, protože by byly ve sporu s dříve provedenými porovnáními. V takovém případě příslušného potomka vynecháme.

TS je ternární. Protože každý ternární strom hloubky k má nejvýše 3^k listů, má TS hloubku nejméně log₃(n).

[^1] https://www.youtube.com/watch?v=RGuJga2Gl_k