Na vstupu máme N prvků. Připravíme si druhé pole na N výsledků, ve kterém zatím nic není. Pak vezmeme jeden po druhém každý prvek na vstupu, najdeme místo, kam patří mezi dosavadní výsledky, a vložíme ho tam. Všechny následující výsledky přitom musíme posouvat, takže nám vložení každého prvku trvá až O(N). Setřídění všech N prvků tedy trvá O(N2).
Zkusíme se vyhnout tomu posouvání: budeme do pole vkládat prvky rovnou od nejmenšího po největší. Nejmenší prvek najdeme pokaždé snadno tak, že v čase O(N) projdeme celé vstupní pole. Takhle nalezený prvek dáme vždy na výstup a nějak si jej ve vstupním poli označíme, abychom jej nevypsali příště znovu. Můžeme to udělat tak, že jej nahradíme prvkem z konce vstupu a prohlásíme, že je pole kratší, anebo si prostě zavést pole pravdivostních hodnot a v něm si pro každý prvek výslovně poznamenávat, zda jsme jej už vypsali. Složitost bude tak jako tak O(N2).
Prochází pole od začátku do konce a pokud je dvojice sousedních prvků ve špatném pořadí, prohodí je. Tohle se opakuje N-krát; potom už určitě není co prohazovat a můžeme navrátit výsledek.
Nabízí se dvě zlepšení. Při troše štěstí už po pár prvních průchodech setřídíme celé pole a nebude co prohazovat. V tu chvíli už opravdu můžeme skončit; vyplatí se tedy pamatovat si, jestli jsme při aktuálním průchodu něco prohodili. Druhé zlepšení vychází z toho, že po i-tém průchodu bude na konci pole setříděných prvků od největšího. Například, po prvním průchodu se určitě největší prvek dostane na konec pole. Když na to vezmeme ohled, můžeme každý průchod skončit právě na i-tém prvku a věřit, že všechny další jsou už setříděné.
V nejlepším případě (když dostaneme už setříděné pole) nám to pomůže hodně, algoritmus proběhne v lineárním čase. To ale nikoho moc nezajímá, protože v nejhorším (a v průměrném také) to běží pořád v O(N2).
Mergesort čili třídění sléváním je založený na tom, že dokážeme rychle ze dvou utříděných seznamů rychle vyrobit jeden velký utříděný seznam. Stačí totiž, když se díváme se vždy na první prvek z obou seznamů; ten menší z příslušného seznamu odebereme a přidáme do pole na výsledky. Až jeden ze seznamů vyprázdníme, přidáme všechno, co zbývá v tom druhém. Může to trochu připomínat třídění přímým výběrem s tím, že víme, kde nejmenší prvky hledat. Slévání trvá O(N), kde N je celkový počet prvků: po každém porovnávání získáme jeden utříděný.
Samotný algoritmus pak běží například tak, že celé vstupní pole rozdělíme na poloviny a ty rekurzivně utřídíme Mergesortem. Pokud je pole na vstupu jen jediný prvek, rekurze se zastaví a navrátí pole nepozměněné: takové pole je jistě utříděné. Když se pak rekurze dostane zase až zpátky nahoru, slije dvě pole velikosti N/2 a navrátí utříděné pole. To je krásná ukázka metody rozděl a panuj.
Pro rozbor složitosti se vyplatí nakreslit si strom rekurzivních volání:
V horní polovině obrázku dělíme vstup a rekurzivně voláme Mergesort, ve spodní jej sléváme a vracíme se z rekurze. Je vidět, že v každé vrstvě rekurze je každý prvek právě jednou, a protože je všechno lineární, strávíme tedy O(N) času v každé vrstvě celkem. Snadno také vidíme, že vrstev je log2(N), celková složitost tedy bude O(N·log(N)).
Quicksort je také založený na metodě rozděl a panuj, tedy rekurzivně volá sám sebe na řešení úloh zhruba polovičních. V každé vrstvě zvolíme jeden prvek pole (budeme mu říkat pivot) jako dělící hodnotu a prvky v poli přeházíme tak, aby na začátku byly všechny menší než pivot, potom pivot samotný a za ním všechny větší nebo rovné. To se dá udělat v lineárním čase a bez použití další paměti, podrobněji rozebereme níže. Potom se Quicksort zavolá na utřídění levé části a pravé části, pivot už zůstane na místě.
Rekurze končí opět ve chvíli, když dostane ke zpracování jediný prvek (nebo dokonce prázdný seznam). Každý prvek se za běhu algoritmu jednou stane pivotem a díky tomu vlevo od něj budou v celém poli prvky jen menší a vpravo jen větší nebo rovny: to znamená, že je pole nakonec utříděné.
S časovou složitostí je to trochu složité. Neřekli jsme, jak vybírat "jeden prvek pole", a přitom na tom hodně záleží: když máme smůlu a vybereme vždy ten nejmenší, vyrobili jsme obyčejné třídění přímým výběrem a to bude trvat O(N2). Sice existuje algoritmus, který zvolí pivot dokonale, ale pro praktické účely je nesmyslně složitý; v běžném životě nám stačí doufat, že budeme mít trochu štěstí, a pivot volit prostě náhodně.
Quicksort totiž má dobrou časovou složitost v průměrném případě. To je termín, který radši nebudeme zavádět moc formálně; je to průměrný čas přes všechny možné vstupy dané velikosti. Složitost pak vychází z toho, že v polovině případů se při výběru bude větší z rozdělených částí menší než tři čtvrtiny, takže podobně jako u Mergesortu skončí rekurze po logaritmicky mnoha vrstvách a v průměrném případě má složitost O(N·log(N)).
Prakticky se používá asi ze všech algoritmů nejčastěji, protože se dá napsat tak, aby běžel hodně rychle na skutečných počítačích, naprosto prakticky vzato. Taky má výhodu, že při práci nepotřebuje žádné vedlejší pole (narozdíl od Mergesortu, například).
Jak tedy prakticky rozdělit pole na dvě části podle pivotu? Všechno zařídíme vyměňováním prvků po dvojicích. Nejdřív uklidíme pivot na konec zpracovávané části pole (prohodíme jej s posledním prvkem). Zbytek pole projdeme zároveň dvěma indexy: jedním zleva, budeme mu říkat L, druhým zprava, tomu říkejme R. Snažíme se, aby prvky vlevo od L byly menší než pivot a vpravo od R byly větší nebo rovny. Oba indexy posouváme co nejblíž k sobě, dokud to platí; zastavíme je oba na prvním prvku, který je špatně. Tyhle dva prvky ale můžeme prohodit a pokračovat. Skončíme ve chvíli, kdy L = R a je hotovo; dokonce můžeme snadno i zjistit, kde je předěl mezi oběma částmi (bude nejvýš jeden prvek vedle obou indexů). Pak vrátíme pivot doprostřed pole a zavoláme Quicksort na obě části zvlášť.
Jen jako takový bonus, tady máte Quicksort v celé své kráse zapsaný v Ruby:
def swap(pole, i, j)
pole[i], pole[j] = pole[j], pole[i] end
def quicksort(pole, zacatek, konec)
return if zacatek >= konec
swap(pole, zacatek+rand(konec-zacatek), konec)
pivot = pole[konec]
l, r = zacatek, konec-1
while l < r do
l += 1 while l < r and pole[l] < pivot
r -= 1 while l < r and pole[r] >= pivot
swap(pole, l, r) if l < r
end
r += 1 if pole[r] < pivot
swap(pole, r, konec)
quicksort(pole, zacatek, r-1)
quicksort(pole, r+1, konec)
end
pole = 10.times.map {rand 100}
quicksort(pole, 0, pole.length-1)
pole
Bucketsort, neboli přihrádkové třídění, je ve své podstatě hrozně jednoduchý. Když víme, že budeme třídit celá čísla v nějakém rozsahu, dejmetomu od 0 do M-1, zavedeme si pole M přihrádek (pro každou možnou hodnotu jednu) a prvky na vstupu do nich prostě naskládáme. Když pak přihrádky projdeme zleva, přečteme prvky rovnou seřazené. To je všechno, časová složitost je tedy lineární; má to ale háček (jinak bychom se tak pečlivě nevěnovali ostatním algoritmům). Na začátku potřebujeme vyrobit pole dlouhé M a na konci ho celé projít. Dokud jsou čísla zhruba stejně velká, jako je jejich počet, je to v pohodě, ale někdy to nemusí být pravda a pak by Bucketsort trval věky, a navíc by zabral nehorázné množství paměti. Obecně tedy napíšeme, že složitost je O(M+N), kde N je počet čísel na vstupu a M je rozsah jejich hodnot.
Co je to přihrádka? Nějaké maličké pole, do kterého se ale vejdou všechna čísla s danou hodnotou. Můžeme pro ni použít libovolné pole, které jde zvětšovat: v Ruby je to typ Array, v C++ vector (s ním se ale pracuje trochu složitěji). Taky je dobrý spojový seznam, někdy je pohodlnější ho použít (a může to být i rychlejší).
Opět malý bonus: dá se elegantně zařídit, abychom všechny přihrádky mohli mít rovnou v jednom velkém poli velikosti N, takže je pak ani nebudeme muset dál zpracovávat a můžeme navrátit výsledek. Vyžaduje to ale spočítat si předem, jak bude ve výsledku každá přihrádka velká. To můžeme udělat podobným algoritmem, kterému se někdy říká Counting sort a místo přihrádek má prostě čísla vyjadřující, kolikrát jsme na danou hodnotu sáhli. Když tohle spočítané máme, už si snadno vyrobíme N indexů do pole na výsledky tak, aby za každým bylo právě akorát volného místa. Když do výsledků zapisujeme, příslušný index vždycky použijeme a posuneme o jedna doprava.