Zhrnutie na Triedenie vkladaním (insertion sort)
Triedenie vkladaním (Insertion Sort): Kompletný Sprievodca
Triedenie vkladaním (Insertion Sort)
Vitajte pri štúdiu Triedenia vkladaním! Tento algoritmus je jedným z najzákladnejších a najintuitívnejších triediacich algoritmov v informatike. Hoci pre veľmi rozsiahle dátové súbory existujú efektívnejšie metódy, triedenie vkladaním je skvelým východiskovým bodom pre pochopenie základných princípov triedenia a má svoje praktické využitie, najmä pri práci s malými súbormi dát alebo s dátami, ktoré sú už čiastočne usporiadané.
Princíp fungovania
Predstavte si triedenie kariet v ruke – to je skvelá analógia pre pochopenie triedenia vkladaním. Keď dostanete balíček neusporiadaných kariet a chcete ich usporiadať napríklad od najmenšej po najväčšiu, robíte to podobne ako Insertion Sort.
Začnete s prvou kartou, ktorú držíte. Tá je sama o sebe usporiadaná, keďže je jediná. Potom vezmete druhú kartu a porovnáte ju s prvou. Ak je menšia, vložíte ju pred prvú. Ak je väčšia, necháte ju za prvou. Už máte usporiadané prvé dve karty.
Následne vezmete tretiu kartu. Tú porovnáte s už usporiadanými kartami a nájdete pre ňu správne miesto. Ak je potrebné, posuniete väčšie karty doprava, aby ste uvoľnili priestor pre novú kartu. Tento proces opakujete pre každú ďalšiu kartu, kým všetky karty nie sú správne usporiadané a celý balíček je zoradený.
Definícia: Triedenie vkladaním (Insertion Sort) je jednoduchý triediaci algoritmus, ktorý pracuje na princípe postupného vkladania prvkov do už usporiadanej časti zoznamu. Zoznam je logicky rozdelený na usporiadanú a neusporiadanú časť.
Podrobný proces s príkladom
Algoritmus triedenia vkladaním rozdeľuje pole, ktoré chceme usporiadať, na dve logické časti:
- Usporiadaná časť: Obsahuje prvky, ktoré sú už na svojich finálnych pozíciách vzhľadom k sebe navzájom.
- Neusporiadaná časť: Obsahuje prvky, ktoré ešte neboli spracované.
Na začiatku je usporiadaná časť tvorená iba prvým prvkom poľa, zatiaľ čo zvyšok poľa tvorí neusporiadanú časť. V každej iterácii algoritmus vezme prvý prvok z neusporiadanej časti (nazývaný „kľúč“) a postupne ho vkladá na správne miesto do už usporiadanej časti. Aby sa pre kľúč uvoľnilo miesto, prvky v usporiadanej časti, ktoré sú väčšie ako kľúč, sa posúvajú o jednu pozíciu doprava.
Poďme si ukázať konkrétny príklad.
Príklad: Usporiadanie poľa $[5, 2, 4, 6, 1, 3]$ vzostupne
-
Počiatočný stav: $[5 | 2, 4, 6, 1, 3]$ (Usporiadaná časť: $[5]$, neusporiadaná: $[2, 4, 6, 1, 3]$)
-
Iterácia $i = 1$ (kľúč = $2$):
- Porovnávame $2$ s prvkami v usporiadanej časti zprava doľava.
- Je $5 > 2$? Áno. Posunieme $5$ doprava. Pole je dočasne $[_, 5, 4, 6, 1, 3]$.
- Usporiadaná časť je teraz prázdna pred miestom, kam sa posunul $5$.
- Vložíme $kľúč=2$ na voľné miesto: $[2, 5 | 4, 6, 1, 3]$.
-
Iterácia $i = 2$ (kľúč = $4$):
- Usporiadaná časť: $[2, 5]$. Neusporiadaná: $[4, 6, 1, 3]$.
- Je $5 > 4$? Áno. Posunieme $5$ doprava. Pole je dočasne $[2, _, 5, 6, 1, 3]$.
- Je $2 > 4$? Nie. Zastavíme posúvanie.
- Vložíme $kľúč=4$ na voľné miesto: $[2, 4, 5 | 6, 1, 3]$.
-
Iterácia $i = 3$ (kľúč = $6$):
- Usporiadaná časť: $[2, 4, 5]$. Neusporiadaná: $[6, 1, 3]$.
- Je $5 > 6$? Nie. Kľúč $6$ je už väčší ako posledný prvok usporiadanej časti, takže je na správnom mieste.
- Vložíme $kľúč=6$ na A[3]: $[2, 4, 5, 6 | 1, 3]$.
-
Iterácia $i = 4$ (kľúč = $1$):
- Usporiadaná časť: $[2, 4, 5, 6]$. Neusporiadaná: $[1, 3]$.
- Je $6 > 1$? Áno. Posunieme $6$ doprava. Pole je dočasne $[2, 4, 5, _, 6, 3]$.
- Je $5 > 1$? Áno. Posunieme $5$ doprava. Pole je dočasne $[2, 4, _, 5, 6, 3]$.
- Je $4 > 1$? Áno. Posunieme $4$ doprava. Pole je dočasne $[2, _, 4, 5, 6, 3]$
Zaregistruj sa pre celé zhrnutieUž máš účet? Prihlásiť sa
Triedenie vkladaním
Klíčová slova: Triedenie vkladaním (Insertion Sort), Algoritmus triedenia vkladaním, Význam simulácie triedenia vkladaním
Klíčové pojmy: Triedenie vkladaním je intuitívny triediaci algoritmus založený na princípe triedenia kariet., Pole je logicky rozdelené na usporiadanú a neusporiadanú časť., V každej iterácii sa prvok z neusporiadanej časti (kľúč) vloží na správne miesto do usporiadanej časti., Prvky v usporiadanej časti, ktoré sú väčšie ako kľúč, sa posúvajú doprava, aby sa uvoľnilo miesto., Algoritmus je efektívny pre malé množiny dát alebo pre čiastočne usporiadané dáta., Najlepší prípad časovej zložitosti je $O(N)$ (pole je už usporiadané)., Priemerný a najhorší prípad časovej zložitosti je $O(N^2)$., Priestorová zložitosť je $O(1)$ (in-place algoritmus)., Je to stabilný triediaci algoritmus, ktorý zachováva relatívne poradie duplikátov., Vhodný pre online triedenie, kde prvky prichádzajú postupne.