Triediace algoritmy a ich výpočtová zložitosť

Triediace algoritmy Bubble-sort, Selection-sort, Insertion-sort, Quick-sort, Radix-sort, Counting-sort, Heap-sort, Merge-sort, pojmy inverzia, stabilný (triediaci) algoritmus, binárny heap (halda) a výpočtová zložitosť problému.

Triediace algoritmy

Častým problémom v algoritmizácií je efektívne (rýchle a pamäťovo nenáročné) triedenie množiny údajov, hľadanie najväčšieho a najmenšieho čísla (respektíve, maximálnej a minimálnej hodnoty), hľadanie mediánu (prostrednej hodnoty) a modusu (hodnoty s najčastejším výskytom) a podobne.

Majme napríklad množinu čísiel: $\{5,2,10,1,-6\}$. Ako naprogramovať algoritmus ktorý takúto množinu usporiada od najmenšieho čísla po najväčšie? Touto otázkou sa zaoberali už tvorcovia algoritmov pred nami, a v súčasnosti existuje hneď niekoľko algoritmov. Každý algoritmus má svoju výpočtovú zložitosť – niektoré sú efektívnejšie pri menšom počte vstupných hodnôt, iné sú zamerané pre triedenie veľkého množstva hodnôt. Neexistuje teda definitívna odpoveď pre to, ktorý algoritmus je najlepší (ale samozrejme vo všeobecnosti vždy hľadáme algoritmus s najmenšou zložitosťou, či už časovou alebo pamäťovou).

V príklade vyššie sú uvedené čísla, ale samozrejme triedenie môžeme realizovať nad všetkým čo má pre nás nejakú postupnosť (napríklad: abecedný zoznam, zoradiť veľkosti objektov od najväčšieho po najmenší, spektrum farieb, triedenie dátumov a podobne). Neexistuje algoritmus ktorý dokáže realizovať triedenie súčasne na všetkých možných množinách prvkov (napríklad, usporiadanie písmen na klávesnici je iné ako abecedná postupnosť tých istých písmen), preto tieto algoritmy väčšinou prispôsobujeme našim potrebám. No pre jednoduchosť budeme v našich algoritmoch triediť iba postupnosti čísiel.

Bubble-sort

Za asi najznámejší triediaci algoritmus sa považuje Bubble-sort ("bublinové triedenie"). Z implementačného hľadiska je to vcelku jednoduchý algoritmus, ktorého princíp spočíva v postupnej výmene prvkov s nesprávnym poradím, pričom každý prvok "vybublá" na správne miesto.

V príklade vyššie je na vstupe pole s 5 číslami. Algoritmus bubble sort obsahuje dva vnorené cykly:

1. Vonkajší cyklus zabezpečuje prechod od posledného indexu poľa k prvému. Je to preto, že s každou iteráciou v tomto cykle je garantované, že sa usporiada práve jedno číslo ("vybublá", preto sa tento algoritmus nazýva bubble-sort). Je zbytočné kontrolovať čísla, ktoré už boli správne vytriedené – preto tento cyklus začína od konca a i sa s každou iteráciou znižuje.
2. Vonkajší cyklus je ten, ktorý realizuje triedenie (porovnávanie dvoch susedných prvkov). Ak je prvý prvok väčší ako prvok ktorý nasleduje, tak sa vymenia. S každou iteráciou sa najväčšie prvky budú posúvať doprava, takže pole bude zoradené od najmenšieho po najväčší (vzostupne). Ak je potrebné čísla zoradiť naopak (od najväčšieho po najmenší, teda zostupne), tak stačí obrátiť znak porovnania (zmeniť podmienku na if pole[j] < pole[j + 1]).

Je to v podstate algoritmus, ktorý posúva maximálne prvky doprava (alebo doľava, ak triedime zostupne), čím sa prvky zotriedia ("vybublajú") na správne miesto.

Algoritmus bubble-sort má časovú výpočtovú zložitosť $O(n^2)$ (v najhoršom prípade), je to jeden z najmenej efektívnych algoritmov. Používame ho napríklad vtedy, keď:

• Triedime menší počet hodnôt a teda takáto výpočtová zložitosť je pre nás akceptovateľná;
• Nevieme naprogramovať niečo lepšie;

Na nasledujúcej úlohe si môžeme skúsiť bubble-sort naprogramovať v Pythone:

Inverzia

Inverzia je dvojica prvkov, ktoré majú zlé poradie (v závislosti od toho, ako by sme chceli aby boli prvky usporiadané).

Napríklad, ak máme množinu čísiel $\{1,3,2,4,5\}$ ktorá má byť zoradená od najmenšieho čísla po najväčšie, tak dvojica prvkov $\{3,2\}$ má zlé poradie. Teda, môžeme povedať že táto množina má 1 inverziu. Ak by malo byť pole zoradené od najväčšieho čísla po najmenšie, tak toto pole má hneď 9 inverzií (aby bolo pole usporiadané, tak by sme museli spraviť 9 výmien).

Existuje algoritmus, podľa ktorého dokážeme zistiť počet inverzií. Pre pole vyššie by sme postupovali takto (pokiaľ by pole malo byť usporiadané od najväčšieho po najmenší):

1. Vyberieme si stranu z ktorej začneme – buď od ľavej strany alebo od pravej. Povedzme, že si vyberieme ľavú. Prvým prvkom v poli zľava je číslo $1$.
2. Spočítame, ktoré prvky na pravej strane od 1 sú väčšie ako 1. Sú to štyri čísla: $\{3,2,4,5\}$.
3. Ak sme vyčerpali všetky čísla, presunieme sa o jedno miesto doľava a zopakujeme postup. Od čísla 3 sú napravo väčšie dve čísla: $\{4,5\}$. Od čísla 2 sú to opäť tie isté dve čísla. Od 4 je väčšie jedno číslo ($5$).
4. Nakoniec iba spočítame všetky väčšie čísla napravo od každého čísla (to, čo sme teraz zisťovali). Teda: $4+2+2+1=9$ inverzií.

Ak by sme mali usporiadať pole opačne (od najmenšieho po najväčší), postupovali by sme rovnako – iba s tým rozdielom, že by sme hľadali prvky ktoré sú na pravej strane menšie ako aktuálne číslo.

Inverzie sa vyskytujú vo všetkých štruktúrach ktoré nie sú správne zoradené a od ktorých očakávame nejaké poradie. Môže to byť napríklad abecedný zoznam mien, zoznam objektov ktoré majú byť zoradené podľa veľkosti ale aj postupnosť dní v týždni – všetko, čo má nejaké poradie.

ℹ️

Poznámka: predpokladáme, že pri odstraňovaní inverzií smieme meniť iba dva susedné prvky (presne ako v bubble-sorte).
Počet inverzií môžeme zistiť pomocou algoritmu v bubble-sorte tak, že vytvoríme na začiatku premennú ktorá predstavuje počet inverzií (na začiatku má hodnotu 0), a toto počítadlo zvýšime vždy o 1 keď v bubble-sorte vymeníme dva susedné prvky. Po ukončení vonkajšieho cyklu bude táto premenná obsahovať počet inverzií pre dané pole.

Úlohy pre určenie počtu inverzií

1 Urči počet inverzií v nasledujúcich množinách čísiel, ktoré majú byť zoradené vzostupne (od najmenšieho po najväčší (odpovede píš číslom, napríklad: 1)

$\{1,3,2\}$, počet inverzií: .

$\{12,5,8,0,4\}$, počet inverzií: .

$\{1,2,3,4,5\}$, počet inverzií: .

2 Koľko inverzií je v nasledujúcom zozname dní v týždni, ak chceme aby boli dni zoradené správne podľa poradia (od Pondelka po Nedeľu)?

Pondelok, Streda, Utorok, Piatok, Nedeľa, Štvrtok, Sobota

Počet inverzií:

Selection-sort

Selection-sort (triedenie výberom) algoritmus vyberá z poľa prvkov najmenší prvok a presunie ho na začiatok.

Výpočtová zložitosť tohto algoritmu je $O(n^2)$. Vo všeobecnosti je rýchlejší ako bubble-sort, avšak pomalší ako insertion-sort.

Insertion-sort

Insertion-sort (triedenie priamym vkladaním) používa jednu časť triedeného poľa pre ukladanie už vytriedených hodnôt a druhú časť toho istého poľa pre hodnoty ktoré ešte nemajú správne poradie. Princíp je podobný ako pri selection-sorte.

Časová výpočtová zložitosť je $O(n^2)$. Avšak narozdiel od selection-sortu, rýchlosť insertion-sortu závisí od vstupného poľa – pre takmer utriedené pole prebehne veľmi rýchlo.

Quick-sort

Ako už napovedá názov, quick-sort je jeden z najrýchlejších triediacich algoritmov. Quick-sort funguje vo všeobecnosti takto:

1. Z poľa hodnôt sa vyberie jeden prvok ako pivot;
2. Zvyšok poľa sa zoradí tak, že hodnoty menšie ako pivot budú naľavo od neho a hodnoty väčšie ako pivot budú napravo;
3. Pivot sa vymení s prvým prvkom v podmnožine s väčšími hodnotami tak, aby pivot spadol medzi menšie a väčšie hodnoty – to rozdelí pôvodné pole na dve podmnožiny, kde menšie prvky sú naľavo a väčšie napravo;
4. Celý postup sa rekurzívne opakuje pre obe podmnožiny menších prvkov naľavo a väčších prvkov napravo. Ak nezostane žiadna podmnožina pre ďalšie triedenie, pole je zoradené a rekurzia sa ukončí (triviálny prípad).

Implementácia quick-sortu je komplexnejšia, preto pripájam už hotový algoritmus v Pythone:

Časová výpočtová zložitosť algoritmu quick-sort je v najhoršom prípade $O(n\times lo{g}_{2}n)$, avšak v priemernom prípade je to iba $\mathrm{\Theta }(n\times lo{g}_{2}n)$, preto je v priemere oveľa efektívnejší ako ostatné algoritmy a patrí medzi najrýchlejšie triediace algoritmy.

Radix-sort

Radix-sort je triediaci algoritmus, ktorý triedi väčšie číselné hodnoty na základe ich cifier, začína od najmenej významnej číslice (sprava doľava). Radix predstavuje základ čísla – v našej (desiatkovej) číselnej sústave máme 10 číslic: od 0 po 9.

Výpočtová zložitosť tohto algoritmu sa dá všeobecne uviesť ako $O(n\times k)$, kde $n$ je počet hodnôt ktoré sa majú vytriediť a $k$ predstavuje počet cifier v najväčšej hodnote (z $n$). Najlepším prípadom je ten, keď má tento algoritmus veľa hodnôt pre triedenie ale všetky hodnoty majú nízky počet číslic (napríklad, triedenie 1 milióna hodnôt ktoré majú rozsah 0 – 999, teda maximálne 3 cifry). V takýchto prípadoch sa časová výpočtová zložitosť môže zjednodušiť iba ako $O(n)$.

Radix-sort je algoritmus, ktorý by pre správne fungovanie mal byť naprogramovaný ako stabilný.

Stabilita triediaceho algoritmu

Algoritmus triedenia sa považuje za stabilný, ak sa po zoradení zachová relatívne poradie rovnakých prvkov. Nestabilný algoritmus zachovanie tohto poradia negarantuje.

Povedzme napríklad, že máme zoznam písmen abecedy ktoré obsahujú určitú hodnotu (môže to byť napríklad počet ľudí ktorí považujú toto písmeno za ich obľúbené). Chceme tento zoznam zoradiť od najobľúbenejšieho písmena po najmenej obľúbené. Ak majú dve susedné písmená rovnakú obľúbenosť, zoradíme ich podľa ich abecedného poradia.

Majme napríklad písmená "K" a "L", pričom obidve majú hodnotu 240. Stabilný algoritmus správne zoradí písmená ako "K" a za ním bude nasledovať "L", avšak nestabilný algoritmus (ktorý triedi iba na základe obľúbenosti a neberie ohľad na abecednú postupnosť) by ich mohol zoradiť ako "L" a "K", čo je avšak nesprávne pretože nie je zachovaná relatívna postupnosť prvkov (na základe obľúbenosti ako primárneho zoradenia) a takýto algoritmus je nestabilný.

Counting-sort

Tento algoritmus usporiada prvky v množine tak, že spočíta koľkokrát sa tam daný prvok nachádza. Je to užitočné, ak máme veľa opakujúcich sa hodnôt a malú rôznorodosť dát. V najhoršom prípade má výpočtovú zložitosť $O(n^2)$.

Heap-sort

Heap-sort (haldové triedenie) je triediaci algoritmus, ktorý využíva heap (haldu) pre efektívne triedenie prvkov. Je vnímaný ako optimalizácia selection-sortu, pretože heap nám umožní rýchlo nájsť v poli minimálnu (alebo maximálnu) hodnotu pre zámenu v $O(lo{g}_{2}n)$ čase namiesto $O(n)$. V dôsledku toho má tento algoritmus celkovú výpočtovú zložitosť $O(n\times lo{g}_{2}n)$.

Heap (halda)

Heap (halda) je dátová štruktúra, ktorá spĺňa vlastnosti heapu (haldy). Je vhodná pre prípady keď potrebujeme častokrát uchovávať maximálny (alebo minimálny) prvok v množine prvkov, pretože tento prvok sa vždy v halde nachádza na vrchu.

Binárny heap je teda strom prvkov (hierarchia), v ktorom je ako koreň vždy najväčší (max-heap) alebo najmenší (min-heap) prvok. Ak pridáme alebo odoberieme nejaký prvok, vlastnosti haldy sa postarajú o to, aby bol na vrchu vždy najväčší prvok.

Haldu môžeme reprezentovať aj lineárne, ako pole prvkov, ak sú splnené nasledovné podmienky:

• Najväčší (v max-heap) alebo najmenší (v min-heap) prvok je v poli vždy prvý;
• Potomkovia akéhokoľvek rodiča sú v min-heap vždy väčší ako rodič (alebo menší, v max-heap);
• Musí to byť binárna štruktúra, to znamená že každý rodič musí mať práve dvoch alebo žiadneho potomka;

Ďalej platí, že:

• Ľavý potomok prvku s indexom $i$ sa nachádza na indexe $(2\times i)+1$;
• Pravý potomok prvku s indexom $i$ sa nachádza na indexe $(2\times i)+2$;
• Rodič prvku $i$ sa nachádza na indexe $\frac{(i-1)}{2}$ (zaokrúhlené nadol);

Napríklad, pole $\{2,3,4,5,7\}$ je min-heap – rodičom je prvok 2, potomkovia sú 3, 4. 3 má ďalších dvoch potomkov: 5 a 7. Táto halda môže byť vizualizovaná nasledovne:

Úlohy pre haldu

Rozhodni, akou haldou sú nasledujúce množiny prvkov:

Syntaktická chyba

1 $\{8,7,5,5,4\}$

	max-heap
	min-heap
	nie je halda

2 $\{2,4,7,9\}$

	max-heap
	min-heap
	nie je halda

3 $\{12,0,0,0,12\}$

	max-heap
	min-heap
	nie je halda

4 $\{42\}$

Merge-sort

.

« Asymptotické hranice výpočtovej zložitosti

Typické algoritmické problémy a ich spôsoby riešenia »