Zadání úlohy

Zadaný je seznam hodnot. U každých dvou dovedeme určit, která je menší, anebo, že mají stejnou hodnotu. Některé algoritmy pracují s jednodušším zadáním: například, že zadané hodnoty jsou čísla. Program má hodnoty vrátit v pořadí od nejmenší po největší.

Třídění v kvadratickém čase

Přímý výběr

Pokaždé najdeme nejmenší hodnotu v seznamu, tu vyndáme a uložíme na konec výstupního seznamu.

Když budeme opatrní, nemusíme nic kopírovat: vystačíme se vstupním seznamem a vyměňováním hodnot v paměti. Řekneme si, že po k krocích výpočtu je na začátku seznamu k hotových, utříděných hodnot, a následujících (n − k) hodnot je zbývající vstup. Vyměníme nejmenší hodnotu ze zbývajícího vstupu s hodnotou na (k + 1)-té pozici. Potom prvních (k + 1) hodnot v seznamu je utříděných a napravo zbývá (n − k − 1) zamíchaných hodnot vstupu. Po n takových krocích máme hotovo, a každý krok trvá O(n) kvůli hledání nejmenší hodnoty, takže celý algoritmus běží v O(n2).

Přímé vkládání

Postupně vezmeme nějakou hodnotu ze vstupu, najdeme, kam ve výstupu patří, a uděláme jí tam místo. Tohle je asi způsob, jakým lidé většinou třídí karty.

Abychom ušetřili kopírování v paměti, můžeme zase nechat výstupní seznam růst na začátku toho zadaného. Vyndáme k-tou hodnotu ze seznamu a zapamatujeme si ji. Pak najdeme nalevo od ní blok (hotových) hodnot, které jsou větší než ta naše, a posuneme je všechny o jednu pozici doprava. Nalevo od toho bloku zbude volné místo, na které můžeme uložit tu zapamatovanou hodnotu.

Najít blok a posunout ho trvá O(n), musíme to udělat n-krát, celkově O(n2).

Třídění v lineárním čase

V lineárním čase nejde třídit zdaleka všechno. Budeme proto třídit čísla – případně, nějaké větší balíky dat označené čísly.

Počítání hodnot

Když je na vstupu n čísel rozumné velikosti, řekněme 0n, můžeme si prostě spočítat, které se vyskytuje kolikrát, a pak je podle toho záznamu vypsat. Potřebujeme k tomu zjevně pomocnou paměť tak velkou, jak vysoké je největší číslo na vstupu.

Přihrádkové třídění

Abychom mohli třídit čísla do menšího počtu přihrádek (a ušetřili tak paměť), nestačí si pamatovat jejich počet, budeme je muset v přihrádkách ukládat jednotlivě. Každá přihrádka tedy bude seznam a čísla do nich postupně překopírujeme; to zabere paměť stejně velkou jako vstup, plus trochu režijních nákladů za každou přihrádku. Rozdělit čísla trvá O(n), nachystat přihrádky trvá O(počet přihrádek). Výsledek je ale utříděný jen částečně, jak to naše přihrádky dovolují.

Radix sort

Setřídíme čísla přihrádkově nejdřív podle poslední číslice, pak podle předposlední a tak dál, až k nejvyššímu řádu. Díky tomu, že se pořadí v rámci každé přihrádky zachovává, budou nakonec čísla správně seřazená. Přihrádek potřebujeme deset (nebo 16, nebo 256, podle chuti), což nezávisí na n. Celý postup potřebujeme opakovat tolikrát, abychom prošli všechny číslice, což na n taky nezávisí. Celková časová složitost je tedy O(n).

Ještě probereme několik algoritmů, které běží v O(n log(n)).