Predstavte si, že máte zoradiť zoznam ľudí podľa abecedy. Pre pár desiatok ľudí je to ešte zvládnuteľná úloha. Pokiaľ sa už množstvo blíži k stovke alebo tisícke, jednoduché postupy začínajú byť veľmi časovo náročné.

Ukážeme si dva postupy, ktoré sú realizovateľné aj pomocou počítačového programu. Prvý z nich bude jednoduchý, ale pomalý. Druhý využíva menší trik, ale na druhej strane bude rýchlejší.

 

Oba postupy majú spoločnú jednu vlastnosť. Využívajú len to, že keď sa pozrieme na dva objekty, tak vieme povedať, ktorý z nich má byť skôr v poradí – porovnáme ich. Tu predpokladáme, že porovnávanie je korektné, to znamená, že ak a<b, b<c, tak aj a<c. Uvedomme si, že pri takom bežnom triedení mien využívame napríklad aj to, že ľudia, ktorých meno začína na K, budú určite v poradí skôr ako tí, ktorých meno začína na R.

Triedenie výberom minima

Majme dva zoznamy. V prvom sú neutriedené objekty, druhý je zatiaľ prázdny, ale nakoniec v ňom budú všetky objekty utriedené (a prvý sa vyprázdni).

V každom kroku zoberieme z prvého zoznamu ten objekt, ktorý má byť najskôr v poradí, a presunieme ho do druhého zoznamu. Takže najskôr presunieme ten objekt, ktorý má byť prvý, potom druhý objekt v poradí atď.

Ukážka triedenia výberom minima postupne v šiestich krokoch. Ľavý stĺpec je vstupný (neutriedený) zoznam. Pravý stĺpec je výstupný (utriedený) zoznam.

Ako dlho nám to bude trvať? Majme na začiatku v prvom zozname 5 objektov. Najprv musíme prejsť všetkých 5 a z nich vybrať najmenší a ten presunúť. Potom sa musíme pozrieť na zvyšné 4 objekty v prvom zozname, vybrať z nich najmenší a presunúť ho atď. Nakoniec ostane posledný objekt, na ktorý sa musíme pozrieť a presunúť ho. Celkovo vykonáme  5+4+3+2+1=15 pozretí. Navyše vykonáme ešte 5 presunov. Pokiaľ by objektov bolo n, tak by sme urobili n+(n-1)+...+3+2+1+n=(n^2+3n)/2 operácií. Takto utriediť milión objektov by nezvládol v rozumnom čase ani bežný počítač.

Metóda rozdeľuj a panuj alebo triedenie zlievaním

Staré vojenské príručky tvrdia, že taktika „rozdeľuj a panuj“ je jednou z najúčinnejších. Poďme ju aplikovať aj na náš problém. Rozdeľme neutriedený zoznam s n prvkami na dva rovnako veľké zoznamy (ak máme nepárny počet objektov, tak v jednom zozname bude o jeden objekt viac). Utrieďme každý zoznam a nakoniec ich spojme dokopy.

Ak máme dva utriedené zoznamy a miesto na konečný utriedený zoznam, tak v každom kroku sa pozrieme na prvé objekty v oboch zoznamoch (tam, kde sú tie, ktoré majú byť najskôr v poradí) a vyberieme ten, ktorý má byť skôr v poradí. Ten uložíme na prvé miesto v konečnom výstupnom zozname. Tomuto procesu hovoríme zlievanie.

Ukážka zlievania v piatich krokoch. V dvoch stĺpcoch naľavo sú vstupné zoznamy. Vpravo sa postupne vytvára výstupný zoznam.

Ako dlho trvá zlievanie? V každom kroku sa musíme pozrieť na jeden objekt z každého zoznamu. Keďže chceme premiestniť n objektov do výsledného zoznamu, musíme spraviť n krokov. V každom kroku spravíme jedno porovnanie a jeden presun, čiže veľkosť kroku nezávisí od počtu objektov v zoznamoch. Prvé dva zoznamy utriedime presne tak isto. Každý rozdelíme na dva, utriedime a zlejeme. Takže celé to nakoniec vyzerá tak, že zoznam rozdelíme až na úplne malé zoznamy (zložené z jediného objektu) a začneme ich spájať.

Ukážka triedenia zlievaním. Najprv zoznam rozdelíme na zoznamy s veľkosťou 1. Potom ich postupne začneme spájať.

Ako dlho to trvá? Zoberme si napríklad triedenie 8 objektov, ktoré je na obrázku. V úplne poslednom kroku sme spojili 8 objektov do jedného zoznamu. To zabralo 8 krokov. Úroveň predtým sme spojili objekty do dvoch zoznamov, každý zoznam mal 4 objekty, takže sme spravili 4 + 4 = 8 krokov. Podobným spôsobom zistíme, že na každej úrovni sme spravili 8 krokov. A koľko máme úrovní? Úplne na začiatku máme zoznamy veľkosti 1. Tie na každej novej úrovni spojíme do dvakrát väčších zoznamov a skončíme až vtedy, keď máme úplne všetky prvky v jednom zozname. Takže počet úrovní bude najmenšie prirodzené číslo x, pre ktoré platí 2^x>=n, kde n je počet triedených objektov. Napríklad pre milión objektov bude mať x hodnotu 20. Celkový počet krokov pre milión objektov bude teda 20 miliónov. To už je rozumnejší počet. Celkový počet krokov sa približne rovná n log2 n.

V praxi sa využíva ešte niekoľko algoritmov. Z tých, ktoré sú porovnateľne rýchle ako triedenie zlievaním, spomeňme quicksort a heapsort (triedenie pomocou haldy). Navyše sa dá ukázať, že pokiaľ chceme triediť pomocou porovnávania, tak rýchlejšie ako na n log2 n krokov sa to nedá. Príkladom triedenia bez porovnávania je napríklad triedenie zmlúv podľa roku podpísania, kde máme vopred nachystané miesto pre zmluvy s konkrétnym rokom podpisu. Potom triedenie spočíva v tom, že zoberieme zmluvu a uložíme ju na pripravené miesto.

Vladimír Boža