Triedenie vkladaním napodobňuje spôsob, akým väčšina ľudí prirodzene ukladá karty pri hre. Berieš karty jednu po druhej a každú vložíš na správne miesto medzi karty, ktoré už máš usporiadané v ruke.
Princíp algoritmu
- Začneme s druhým prvkom (prvý prvok je "zoradený sám o sebe").
- Vezmeme aktuálny prvok — nazývame ho kľúč.
- Porovnáme ho so všetkými prvkami vľavo (zoradená časť).
- Posúvame väčšie prvky o jedno miesto doprava.
- Vložíme kľúč na správne miesto.
- Opakujeme od kroku 2 s ďalším prvkom.
Vizualizácia pre [5, 3, 4, 1, 2]:
[5 | 3, 4, 1, 2] → kľúč=3: 3<5, posuň 5 → [3, 5, 4, 1, 2]
[3, 5 | 4, 1, 2] → kľúč=4: 4<5, posuň 5; 4>3, vlož → [3, 4, 5, 1, 2]
[3, 4, 5 | 1, 2] → kľúč=1: posuň 5,4,3 → [1, 3, 4, 5, 2]
[1, 3, 4, 5 | 2] → kľúč=2: posuň 5,4,3; 2>1, vlož → [1, 2, 3, 4, 5]
Implementácia v Pythone
def triedenie_vkladanim(zoznam):
for i in range(1, len(zoznam)):
kluc = zoznam[i] # aktuálny prvok na vloženie
j = i - 1
# Posuň prvky, ktoré sú väčšie ako kľúč, o jedno doprava
while j >= 0 and zoznam[j] > kluc:
zoznam[j + 1] = zoznam[j]
j -= 1
# Vlož kľúč na správné miesto
zoznam[j + 1] = kluc
return zoznam
cisla = [5, 3, 4, 1, 2]
print(triedenie_vkladanim(cisla))
# [1, 2, 3, 4, 5]
Na rozdiel od bublinkového a výberového triedenia je triedenie vkladaním adaptívne — pre takmer zoradené zoznamy je oveľa rýchlejšie. V najlepšom prípade (zoradený vstup) má len N-1 porovnaní.
Krok po kroku — sledovanie kódu
zoznam = [4, 2, 7, 1]
# i=1: kluc=2, j=0
# zoznam[0]=4 > 2 → posuň: [4, 4, 7, 1], j=-1
# vlož kluc na j+1=0: [2, 4, 7, 1]
# i=2: kluc=7, j=1
# zoznam[1]=4, 4 < 7 → nezasahuj
# vlož kluc na j+1=2: [2, 4, 7, 1] (žiadna zmena)
# i=3: kluc=1, j=2
# zoznam[2]=7 > 1 → posuň: [2, 4, 7, 7], j=1
# zoznam[1]=4 > 1 → posuň: [2, 4, 4, 7], j=0
# zoznam[0]=2 > 1 → posuň: [2, 2, 4, 7], j=-1
# vlož kluc na j+1=0: [1, 2, 4, 7]
Výkonnostné charakteristiky
| Prípad | Zložitosť | Popis |
|---|---|---|
| Najlepší | O(N) | Vstup je zoradený |
| Priemerný | O(N²) | Náhodný vstup |
| Najhorší | O(N²) | Vstup je obrátene zoradený |
Výhody triedenia vkladaním
- Efektívne pre malé zoznamy — menej réžie ako zložitejšie algoritmy.
- Adaptívne — rýchle pre takmer zoradené dáta.
- Stabilné — zachováva poradie rovnakých prvkov.
- In-place — nepotrebuje extra pamäť.
- Online — môže triediť prvky, ako prichádzajú (jeden po druhom).
Triedenie vkladaním je základ algoritmu Timsort — hybridného algoritmu, ktorý Python používa pre svoju vstavanú funkciu sorted(). Timsort ho využíva na triedenie malých úsekov dát.
Pre veľké nezoradené zoznamy (tisíce prvkov) je triedenie vkladaním pomalé kvôli O(N²) zložitosti. V takých prípadoch je lepšie použiť vstavaný sorted().
Cvičné príklady
Aké sú výhody triedenia vkladaním oproti bublinkovému triedeniu?
Zobraziť odpoveď
Porovnaj zoznam [1, 2, 3, 4, 5] a [5, 4, 3, 2, 1] — pre ktorý bude triedenie vkladaním rýchlejšie a prečo?