Tento referát sa zaoberá metódou triedenia dát vkladaním, ktorá je efektívna pri priebežnom vkladaní nových prvkov do už usporiadaného poľa. Popisuje kroky potrebné na vloženie nového prvku a poskytuje aj zdrojový kód v C++ na ilustráciu algoritmu.
- Metóda vkladaním je efektívna pre priebežné vkladanie nových prvkov do usporiadaného poľa.
- Prvým krokom je nájsť pozíciu, kam nový prvok patrí, porovnaním s existujúcimi prvkami.
- Druhým krokom je presun všetkých prvkov od nájdenej pozície o jeden index doprava.
- Tretím krokom je vloženie nového prvku na voľnú pozíciu.
- Algoritmus je implementovaný v C++ a zahŕňa funkcie pre jednotlivé kroky vkladania.
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
🤔 Najčastejšie otázky k téme
Aké sú hlavné výhody metódy triedenia vkladaním?
Hlavné výhody metódy triedenia vkladaním sú jej efektívnosť pri priebežnom vkladaní nových prvkov do už usporiadaného poľa a jednoduchá implementácia.
Ako funguje prvý krok algoritmu vkladaním?
Prvý krok algoritmu spočíva v porovnaní nového prvku s existujúcimi prvkami v poli, aby sa našla správna pozícia, kde nový prvok patrí.
Čo sa deje v druhom kroku algoritmu?
V druhom kroku sa presunú všetky prvky od nájdenej pozície o jeden index doprava, aby sa vytvoril priestor pre nový prvok.