Výberové triedenie má iný prístup ako bublinkové: namiesto opakovaného zamieňania susedov hľadá najmenší prvok v nezoradenom zvyšku a presúva ho na začiatok.
Ako funguje?
Algoritmus rozdelí zoznam na dve časti:
- Zoradená časť — na začiatku (spočiatku prázdna)
- Nezoradená časť — zvyšok
V každom kroku nájde minimum nezoradenej časti a presunie ho na koniec zoradenej časti (výmenou s prvým prvkom nezoradenej časti).
Vizualizácia pre [64, 25, 12, 22, 11]:
| Krok | Zoznam | Minimum nezoradených | Výmena |
|---|---|---|---|
| 0 | [64, 25, 12, 22, 11] | 11 (index 4) | 64 ↔ 11 |
| 1 | [11, 25, 12, 22, 64] | 12 (index 2) | 25 ↔ 12 |
| 2 | [11, 12, 25, 22, 64] | 22 (index 3) | 25 ↔ 22 |
| 3 | [11, 12, 22, 25, 64] | 25 (index 3) | 25 ↔ 25 |
| 4 | [11, 12, 22, 25, 64] | hotovo | — |
Implementácia v Pythone
def vyberove_triedenie(zoznam):
n = len(zoznam)
for i in range(n):
# Nájdi index minima v nezoradenom zvyšku
min_index = i
for j in range(i + 1, n):
if zoznam[j] < zoznam[min_index]:
min_index = j
# Vymeň minimum s prvým prvkom nezoradenej časti
zoznam[i], zoznam[min_index] = zoznam[min_index], zoznam[i]
return zoznam
cisla = [64, 25, 12, 22, 11]
print(vyberove_triedenie(cisla))
# [11, 12, 22, 25, 64]
Výberové triedenie robí vždy presne N-1 výmen (jedna výmena na priechod), kde N je počet prvkov. To je oveľa menej výmen ako bublinkové triedenie, ale počet porovnaní je rovnaký — N²/2.
Krok po kroku — sledovanie kódu
zoznam = [3, 1, 4, 2]
# i=0: min_index=0, porovnáme s 1(j=1)→min=1, s 4(j=2)→min=1, s 2(j=3)→min=1
# vymeň zoznam[0] a zoznam[1]: [1, 3, 4, 2]
# i=1: min_index=1, porovnáme s 4(j=2)→min=1, s 2(j=3)→min=3
# vymeň zoznam[1] a zoznam[3]: [1, 2, 4, 3]
# i=2: min_index=2, porovnáme s 3(j=3)→min=3
# vymeň zoznam[2] a zoznam[3]: [1, 2, 3, 4]
# i=3: len jeden prvok zostáva, hotovo
Porovnanie s bublinkovým triedením
| Vlastnosť | Bublinkové | Výberové |
|---|---|---|
| Porovnania | N²/2 | N²/2 |
| Výmeny | Až N²/2 | Vždy N-1 |
| Vhodné pre | Malé zoznamy | Malé zoznamy |
| Stabilné | Áno | Nie |
Výberové triedenie je výhodnejšie, keď je výmena prvkov nákladná operácia (napr. veľké objekty v pamäti). Menší počet výmen môže byť prakticky dôležitý.
Stabilita triedenia
Hovoríme, že algoritmus je stabilný, ak zachováva poradie prvkov s rovnakou hodnotou. Výberové triedenie nie je stabilné:
# Predstav si zoznam dvojíc (číslo, meno) zoradených podľa čísla
zoznam = [(2, "Anna"), (1, "Boris"), (2, "Cecília")]
# Po výberovom triedení podľa čísla môže byť: [(1,"Boris"), (2,"Cecília"), (2,"Anna")]
# Poradie Anny a Cecílie sa mohlo zmeniť!
Rovnako ako bublinkové, aj výberové triedenie má časovú zložitosť O(N²) a je nevhodné pre veľké dáta. Pre tisíce prvkov a viac použi vstavaný sorted() v Pythone, ktorý používa oveľa efektívnejší algoritmus Timsort.
Cvičné príklady
Pre zoznam [5, 2, 8, 1, 9] — ktorý prvok sa presunie na pozíciu 0 po prvom priechode výberového triedenia a ako?
Zobraziť odpoveď
Koľko výmen (swap) vykoná výberové triedenie pre zoznam s 6 prvkami?