Triedenie je proces usporiadania prvkov (čísel, slov, záznamov) do určeného poradia — zvyčajne vzostupného alebo zostupného. Triediace algoritmy patria medzi najdôležitejšie v celej informatike, pretože usporiadané dáta sa oveľa efektívnejšie vyhľadávajú a spracovávajú.
Prečo triedenie záleží
Predstavte si, že hľadáte meno v telefónnom zozname. Keby záznamy neboli zoradené abecedne, museli by ste prehľadávať každý záznam — to by trvalo veľmi dlho. Zoradený zoznam umožňuje oveľa rýchlejšie hľadanie (napríklad binárnym vyhľadávaním).
Triediace algoritmy sa líšia predovšetkým rýchlosťou a množstvom pamäte, ktorú potrebujú.
Bubble Sort (bublinkové triedenie)
Bubble sort je jednoduchý, ale pomalý algoritmus. Opakovane prechádza zoznamom, porovnáva susedné prvky a vymieňa ich, ak sú v nesprávnom poradí. Väčšie prvky „bublajú" na koniec.
Vstup: [5, 3, 8, 1]
Prechod 1: [3, 5, 1, 8]
Prechod 2: [3, 1, 5, 8]
Prechod 3: [1, 3, 5, 8] ← zoradené
Bubble sort má časovú zložitosť O(n²) — pre veľké zoznamy je veľmi pomalý.
Bubble sort sa v praxi skoro nepoužíva kvôli pomalosti. Jeho hodnota je didaktická — ľahko sa pochopí a implementuje, čo ho robí vhodným pre výučbu konceptu triedenia.
Selection Sort (výberové triedenie)
Selection sort rozdeľuje zoznam na dve časti: zoradenú (na začiatku) a nezoradenú (na konci). V každom kroku nájde najmenší prvok v nezoradennej časti a prehodí ho na začiatok nezotriedenej časti.
Vstup: [5, 3, 8, 1]
Krok 1: [1, 3, 8, 5] (1 je minimum, prehodíme s 5)
Krok 2: [1, 3, 8, 5] (3 je minimum, je na mieste)
Krok 3: [1, 3, 5, 8] (5 je minimum, prehodíme s 8)
Výsledok: [1, 3, 5, 8]
Selection sort tiež má zložitosť O(n²), ale robí menej výmen ako bubble sort.
V reálnych aplikáciách sa používajú efektívnejšie algoritmy ako Merge Sort alebo Quick Sort so zložitosťou O(n log n). Väčšina programovacích jazykov má zabudované triediace funkcie, ktoré tieto algoritmy využívajú.
Porovnanie algoritmov
| Algoritmus | Priemerná zložitosť | Vhodný pre |
|---|---|---|
| Bubble Sort | O(n²) | Výučbu, malé zoznamy |
| Selection Sort | O(n²) | Výučbu, malé zoznamy |
| Merge Sort | O(n log n) | Veľké zoznamy, stabilné triedenie |
| Quick Sort | O(n log n) | Väčšina praktických prípadov |
Voľba triediaceho algoritmu závisí od veľkosti dát, dostupnej pamäte a toho, či potrebujeme stabilné triedenie (zachovanie poradia rovnakých prvkov).
Cvičné príklady
Koľko porovnaní vykoná bubble sort v najhoršom prípade pre zoznam s 4 prvkami?