Nedeľník touchIT vážne i nevážne. Nezviazané IT témy na tisíc spôsobov.
Sortovacie, alebo pekne po slovensky aj zoraďovacie či triediace algoritmy, sú celkom esenciálnou súčasťou informačných technológií. Ako ich už názov napovedá, ich účelom je zoradiť dáta podľa nejakých základných vlastností.
Na prvý pohľad sa to nemusí zdať, ale zoraďovacie algoritmy patria k tým úplne najzákladnejším a takisto najdôležitejším prvkom rôzneho softvéru. Nejde len o to zoradiť vaše súbory podľa abecedy, alebo podľa dátumu vytvorenia. Zoraďovať je nutné napríklad výsledky internetového vyhľadávača či pakety, ktorými putuje táto stránka do vášho počítača.
Prakticky od úplných počiatkov počítačov sa problematike zoraďovania venovalo množstvo matematikov a informatikov, ktorí postupom času objavili plejádu veľmi zaujímavých a účinných algoritmov.
Aj keď táto činnosť počítača je vo svojej podstate veľmi jednoduchá a priamočiara, nájsť efektívne a v mnohých prípadoch použiteľné riešenie je neľahká úloha. Mnoho informatikov dodnes považuje problematiku zoraďovania za úplne fundamentálny prvok štúdia algoritmov.
Každý zoraďovací algoritmus má nejaké slabiny a výhody a nové riešenia sa objavujú ešte aj dnes. Jedným z úplne esenciálnych algoritmov je Insertion sort, alebo po slovensky – algoritmus zoraďovania vkladaním.
Ide o veľmi jednoduchý a prirodzený algoritmus, ktorý ľudia často intuitívne používajú aj pri manuálnom zoraďovaní kariet alebo iných objektov (autor animácie je Swfung8). Položky začneme zoraďovať od prvého páru a následne berieme vždy nasledujúci objekt a zaradíme ho do už existujúceho poradovníka na správne miesto.
Jeden z najstarších počítačových zoraďovacích algoritmov, používaný už v 50-tych rokoch minulého storočia, je Bubble sort, čo je v preklade bublinové zoraďovanie.
Bubble sort v akcii. Všimnite si, ako bublinovo postupne vystupujú najväčšie položky dohora
Algoritmus dostal svoje meno podľa toho, že pri každom jeho prechode dátami sú tie najväčšie ešte nezoradené položky tlačené navrch, podobne ako bubliny stúpajú vo vode smerom k hladine.
Bubble sort algoritmus číta hodnoty vždy v pároch a ak sú v nesprávnom poradí, napraví ich. Následne sa posunie o jednu pozíciu ďalej a pár opäť porovná. Keďže v páre sa vždy drží najznámejší najväčší objekt, postupne sa tie väčšie posúvajú dopredu.
Algoritmus pokračuje až dovtedy, dokým už nie je možné prehodiť žiadny pár. V tom momente sú už všetky v správnom poradí a dáta sú zoradené.
Bubble sort je jednoduchý a dobre pochopiteľný algoritmus. Je pri tom vždy úspešný, takže konečný objem dát zoradí vždy v konečnom čase. To ale pravdaže neznamená, že ich zoradí rýchlo. V prípade, že je potrebné zoradiť veľké množstvo položiek (sto, tisíc či milióny), Bubble sort sa rýchlo stane časovo veľmi neefektívny.
Ak chcene proces zoraďovania urýchliť, je potrebné nájsť lepší algoritmus. Jeden z ikonických efektívnych algoritmov vytvoril v 50-tych rokoch minulého storočia geniálny matematik, fyzik a informatik John von Neumann. Neuman sa významnou mierou podpísal na našich znalostiach kvantovej fyziky, funkcionálnej analýzy, teórie množín, štatistiky, hydrodynamiky a takisto informatiky.
Legendárny fyzik, matematik a informatik John von Neumann
Jedným z jeho odkazov je aj zoraďovací algoritmus Merge sort (zoradenie zlučovaním), ktorý sa dá jednoducho prirovnať k prísloviu „Rozdeľ a panuj“.
Algoritmus najprv rozdelí dáta na polovicu, potom na štvrtinu, na osminu a tak ďalej, dokým nedôjde k jednotlivým položkám. Následne začne susedné skupiny opätovne spájať, pričom ich pri zlúčení usporadúva. Takto postupne pokračuje, pričom vždy berie najmenšiu položku z danej dvojice a pokračuje nahor.
Na prvý pohľad by sa mohlo zdať, že Merge sort algoritmus nie je od Bubble sort algoritmu príliš odlišný. Ako náhle však algoritmy začnú zoraďovať väčšie množstvo dát, rozdiel sa okamžite prejaví. Merge sort totiž potrebuje na zoradenie omnoho menej krokov.
Na demonštráciu si pozrite tento priamy súboj, pri ktorom algoritmy zoraďujú rovnaký počet náhodne veľkých dát. Rýchlosť je upravená tak, aby sme mohli súboj sledovať, avšak každý jednotlivý krok trvá algoritmom rovnako, takže podmienky majú totožné.
Merge sort (hore) svojho konkurenta úplne deklasuje. Čím viac dát necháte algoritmom zoraďovať, tým bude náskok Merge sortu väčší.
Existuje nejaký algoritmus, ktorý porazí zas jeho? Jedným z takých je obvykle Shell sort, nazvaný podľa amerického informatika Donalda Shella, ktorý ho navrhol v roku 1959. Ide viac-menej o kombináciu princípov algoritmov, ktoré sme spomenuli ako prvé, teda o Bubble sort a Insertion sort.
Jeho princíp je pekne ukázaný na nasledujúcom videu.
Algoritmus používa rozlične veľké medzery medzi porovnávanými dátami, pričom rozsah postupne znižuje.
Na videu môžete vidieť, že najprv porovná dáta, ktoré sú od seba päť pozícii vzdialené. Ak sú v nesprávnom poradí, vymení ich. Následne začne porovnávať dáta dve pozície od seba. Ak sú v správnom poradí, nechá ich tak. Ak sú zle, vymení ich, avšak tentoraz vždy pri výmene počká a otestuje aj vždy ďalší nasledujúci pár. Následne pokračuje už so susediacimi dátami a zoraďovanie dokončí. Čas zoradenia závisí na rozložení dát a takisto na tom, aké medzery na porovnávanie používa.
V mnohých ohľadoch je najrýchlejší zoraďovací algoritmus Quick sort, ktorý v roku 1961 publikoval britský informatik Tony Hoare. V preklade ide doslova o algoritmus rýchleho zoraďovania a jeho meno nie je v žiadnom prípade prehnané.
Quick sort podobne ako Merge sort pracuje s postupným rozdeľovaním typu „rozdeľ a panuj“ (animácia RolandH). Používa však zaujímavý prvok, nazývaný pivot. Ide o stred otáčania, pri ktorom sa v úvode jedna dátová hodnota stane pivotom a ostatné dáta sa rozdelia na dve časti podľa nej. Jedna časť dát bude väčšia ako pivot a druhá menšia. Následne sa obe skupiny zvolia svojho pivota a rozdelia sa podľa neho. Takto sa pokračuje dovtedy, až dokým nezostanú už jednotlivé samostatné hodnoty.
V takomto okamihu už môže algoritmus ísť nazad smerom hore a dáta menšie ako pivot zoraďovať dopredu a dáta väčšie dozadu. Ako stúpa k ďalším pivotom, dáta prirodzene zostávajú v správnom poradí. Vizualizáciu môžete vidieť na nasledovnom videu.
Aj keď je Quick sort vo väčšine prípadov najrýchlejší, nič také ako najlepší sortovací algoritmus neexistuje. Pri rôznom rozložení dát totiž budú rôzne algoritmy inak rýchle. Dôležitý je pri tom nielen čas, ale aj komplexnosť algoritmu, požiadavky na systémové prostriedky a podobne.
Významným algoritmom je napríklad Heap sort, v preklade doslova zaraďovanie haldou, ktorý patrí k mimoriadne efektívnym a zároveň spoľahlivým. I keď ho Quick sort v priamom súboji obvykle porazí, jeho silnou stránkou je zaručená časová náročnosť.
Jeho autormi sú informatici Robert W. Floyd a J. W. J. Williams, ktorý ho publikoval v roku 1964. Algoritmus využíva dátovú štruktúru, označované ako halda, ktorá sa vyznačuje efektívnym výberom najväčšieho prvku a zároveň efektívnym vložením. Pred samotným zoraďovaním teda algoritmus rýchlo zoradí dáta tak, aby skupiny splňovali vlastnosti haldy.
Priame porovnanie rýchlosti algoritmov môžete pekne vidieť na tomto videu. Opäť treba myslieť na to, že čas je nastavený tak, aby sme video mohli sledovať. Zoradenie takéhoto počtu dát trvá počítaču nanosekundy.
Na začiatku môžete vidieť algoritmy zoraďovať náhodný zhluk dát. Quick sort (v strede) zvíťazí, nasledovaný Shell sortom nad ním a Merge sortom vľavo. Heap sort skončí ako štvrtý, zatiaľ čo Bubble sort je bezkonkurenčne posledný.
V čase 1:07 je vidieť súboj na dátach, ktoré sú vo väčšine prípadov rovnaké. Quick sort konkurenciu deklasuje. Ako ďalší dobehne Shell sort a následne skoro súčasne Merge sort a Heap sort.
V čase 2:08 môžete vidieť zoradenie špeciálneho prípadu, kedy sú všetky dáta v opačnom poradí. Víťazí opäť Quick sort. V čase 3:38 sa ale prejaví jeho slabina, ktorá nastáva v prípade, že dáta sú takmer zoradené (alebo úplne zoradené). Jeho funkcia pivota ho vtedy pekelne zradí, pretože prebehne celá prakticky zbytočne. Naproti tomu základné zoraďovanie vkladaním v podobe Insertion sort, ktoré väčšinou bolo o dosť pomalšie ako ostatné algoritmy, tu jasne zvíťazí.
Z takýchto dôvodov sa obvykle Quick sort nehodí do systémov, ktoré musia reagovať v garantovanom čase. Vtedy je vhodnejší iný algoritmus, ktorý je v priemere síce o niečo pomalší, ale v najhorších situáciách sa tak neprepadne a vždy má vyrovnaný výkon, na ktorý sa dá spoľahnúť (napríklad práve Heap sort).
Na záver ešte pekná prehliadka práce 15 zoraďovacích algoritmov, vtesnaná do niekoľkých minút.
Ak vás algoritmy zaujali, zasúťažiť si s nimi môžete aj sami na peknej animovanej stránke Sorting.at a takisto na stránke Sorting-algorithms.com.
