Triedenie je proces usporiadania prvkov poľa tak, aby ich bolo možné umiestniť vo vzostupnom alebo zostupnom poradí. Uvažujme napríklad pole A = {A1, A2, A3, A4, ?? }, pole sa nazýva vzostupne, ak sú prvky A usporiadané ako A1 > A2 > A3 > A4 > A5 > ? > An .
Zvážte pole;
int A[10] = { 5, 4, 10, 2, 30, 45, 34, 14, 18, 9)
Pole zoradené vo vzostupnom poradí bude dané ako;
A[] = { 2, 4, 5, 9, 10, 14, 18, 30, 34, 45 }
typy počítačov
Existuje mnoho techník, pomocou ktorých je možné vykonávať triedenie. V tejto časti tutoriálu podrobne rozoberieme každú metódu.
Algoritmy triedenia
Algoritmy triedenia sú spolu s popisom popísané v nasledujúcej tabuľke.
| SN | Algoritmy triedenia | Popis |
|---|---|---|
| 1 | Bublinové triedenie | Je to najjednoduchšia metóda triedenia, ktorá vykonáva triedenie opakovaným presúvaním najväčšieho prvku na najvyšší index poľa. Pozostáva z porovnania každého prvku s jeho susedným prvkom a podľa toho ich nahradí. |
| 2 | Triediť vedro | Bucket sort je známy aj ako bin sort. Funguje to tak, že sa prvok rozdelí do poľa, ktoré sa tiež nazýva buckets. V tomto triediacom algoritme sa segmenty triedia jednotlivo pomocou rôznych triediacich algoritmov. |
| 3 | Triediť hrebeňom | Comb Sort je pokročilá forma Bubble Sort. Bublinové triedenie porovnáva všetky susediace hodnoty, zatiaľ čo hrebeňové triedenie odstraňuje všetky hodnoty korytnačiek alebo malé hodnoty blízko konca zoznamu. |
| 4 | Počítanie Triediť | Je to technika triedenia založená na kľúčoch, t. j. predmety sa zbierajú podľa kľúčov, ktoré sú malými celými číslami. Zoradenie počítania vypočíta počet výskytov objektov a uloží jeho kľúčové hodnoty. Nové pole sa vytvorí pridaním predchádzajúcich kľúčových prvkov a priradením k objektom. |
| 5 | Hromadné triedenie | Pri triedení haldy sa udržiava minimálna halda alebo maximálna halda z prvkov poľa v závislosti od výberu a prvky sa triedia odstránením koreňového prvku haldy. |
| 6 | Triedenie vloženia | Ako už názov napovedá, triedenie vložením vloží každý prvok poľa na svoje správne miesto. Je to veľmi jednoduchá metóda triedenia, ktorá sa používa na usporiadanie balíčka kariet pri hraní bridžu. |
| 7 | Zlúčiť triedenie | Zoradenie zlúčením sa riadi prístupom rozdelenia a dobytia, v ktorom sa zoznam najprv rozdelí na množiny rovnakých prvkov a potom sa každá polovica zoznamu triedi pomocou triedenia zlúčením. Zoradený zoznam sa opäť spojí a vytvorí základné triedené pole. |
| 8 | Rýchle triedenie | Rýchle triedenie je najviac optimalizovaný triediaci algoritmus, ktorý vykonáva triedenie v porovnaní O(n log n). Rovnako ako triedenie zlúčením, aj rýchle triedenie funguje pomocou prístupu rozdeľuj a panuj. |
| 9 | Zoradiť Radix | V Radix sort sa triedenie vykonáva tak, ako my triedime mená podľa ich abecedného poradia. Je to lenárny algoritmus triedenia používaný pre Inegers. |
| 10 | Výber Zoradiť | Triedenie výberu nájde najmenší prvok v poli a umiestni ho na prvé miesto v zozname, potom nájde druhý najmenší prvok v poli a umiestni ho na druhé miesto. Tento proces pokračuje, kým sa všetky prvky nepresunú do správneho poradia. Nesie čas chodu O(n2), ktorý je horší ako triedenie vkladania. |
| jedenásť | Shell Sort | Shell sort je zovšeobecnenie typu vkladania, ktoré prekonáva nevýhody triedenia vkladaním porovnaním prvkov oddelených medzerou niekoľkých pozícií. |