Triedenie, po anglicky sorting, iným slovom aj zoraďovanie.
Zoraďovať môžeme len veci, ktoré vieme porovnať (napríklad čísla, písmená). Nemôžeme sa opýtať, či je väčší obrázok, alebo tón c1.
Príklad č.1:
Máme napríklad 3 premenné A, B, C a chceme ich zoradiť podľa veľkosti. Zistíme, ktorá je najmenšia a dáme ju do premennej D. Druhú najmenšiu dáme do premennej E, najväčšiu dáme do premennej F.
V programovaní však často spracúvame veľké množstvá dát (na malé množstvá nepotrebujeme počítač, to vieme aj z hlavy 🙂 ), potrebujeme stovky, tisíce premenných, preto väčšinou zoraďujeme polia. Zoraďovať ich môžeme ľubovoľným spôsobom, môžeme si vymyslieť vlastný algoritmus. Tu popíšeme niektoré už vymyslené a osvedčené algoritmy. Niektoré sú jednoduchšie na pochopenie, pri študovaní odporúčame začať nimi:
Iné sú zložitejšie, vyžadujú mať zvládnuté náročnejšie koncepty, ako napríklad rekurzia, stromy…
- Quicksort
- Heapsort
- Merge sort
Typy triedenia podľa množstva použitej pamäte:
Ak máme pole so 100 prvkami, a chceme ho utriediť podľa príkladu č.1, budeme potrebovat druhé pole so 100 prvkami. Spotrebovaná pamäť je teda 2x väčšia ako počet dát (označujeme to 2xN). Pôvodných 100 prvkov (vo všeobecnosti N prvkov) máme uložených v pamäti veľkosti N (krát konštanta veľkosti dátového typu), čo platí pre všetky algoritmy rovnako. Náročnosť triediacich algoritmov sa teda porovnáva len podľa navyše spotrebovanej pamäte. Pamäťová náročnosť príkladu č.1 je teda O(n).
Najnižšia možná pamäťová náročnosť je 1. Tú majú také triedenia, ktoré prehadzujú prvky v rámci daného poľa, keďže na výmenu 2 prvkov vždy potrebujeme 1 pomocnú premennú. Tu patria napríklad triedenia Bubble sort, Min sort, Heapsort…
Typy triedenia podľa rýchlosti:
Rýchlosť programu závisí od toho, koľko operácii sa má vykonať. Nezaratávame operácie, ktoré sú rovnaké pre každé triedenie, ako napríklad výpis výsledného poľa. Čím sa algoritmy líšia, je to, koľko operácii potrebujeme na samotné utriedenie.
Najnižšia možná rýchlosť je O(n). Tá sa dá dosiahnuť vtedy, ak celé pole utriedime na prvý prechod. Nejde však o porovnávanie prvkov, ale o využívanie indexov.
- Counting sort O(n)
Ostatné algoritmy sú porovnávacie a tie už trvajú dlhšie:
- Heapsort O(n* log n)
- Merge sort O(n* log n)
- Shell O(n* log2 n)
- Selection sort O(n2)
- Bubble sort a jeho varianty O(n2)
- Quicksort, väčšinou je rýchly O(n* log n), ale v určitých prípadoch mu to trvá O(n2)