V predchádzajúcich dvoch častiach boli predstavené metódy triedenia dát optimalizované na rýchlosť. Treťou metódou je metóda vkladaním (vsúvaním), ktorej princíp je vysvetlený v tomto článku.
Predchádzajúce metódy (výberom a výmenou) utrieďovali nezotriedené pole dát naraz. Existuje však množstvo prípadoch, kde sa už do utriedeného poľa vkladá nový prvok.
Typickým prípadom sú napríklad rôzne športové podujatia, s ktorými súvisí zotrieďovanie výkonov na stavových tabuliach. Dáta sa na stavovej tabuli zotrieďujú priebežne.
Predstavme si súťaž v skoku do diaľky. Každý nový výkon sa v priebežnom poradí zapíše do tabuľky. Bolo by neefektívne po každom podanom výkone odznova zoradiť celú tabuľku podľa predchádzajúcich dvoch algoritmov. Preto pri zápise nového prvku do už usporiadaného poľa využívame metódu vkladaním.
Predpokladajme usporiadané n-prvkové pole
a[0] < a[1] < a[2] < a[3] ... a[n-3] < a[n-2] < a[n-1]
Do tohto poľa chceme vložiť nový prvok x.
- 1. krok Najskôr treba nový prvok porovnať so všetkými prvkami v poli, a nájsť pozíciu kam patrí. Všetky indexy poľa prebehneme pomocou cyklu for, pričom aktuálny prvok poľa porovnávame s novým prvkom. Ak platí nerovnosť a[k] >= x, potom prvok x patrí medzi prvky a[k-1] a a[k].
- 2. krok spočíva v presune všetkých prvkov a[k] až a[n-1] o jeden index "do prava" podľa schémy:
a[n] = a[n-1]; a[n-1] = a[n-2]; a[n-2] = a[n-3]; a[n-3] = a[n-4];
- 3. krok Medzera ktorá vznikne presunom v 2. kroku (a[k]) sa vyplní novým prvkom. Pre lepšie pochopenie algoritmu viď obrázok.
Nasleduje zdrojový kód algoritmu v c++:
#include #include #include
int n; int pole[10];
void vypis(int arr[]) { for (int i=1;i