Triediace algoritmy

Zoradiť pár čísel od najmenšieho po najväčšie zvládne každý. Počítač na to potrebuje presný postup zložený z jednoduchých krokov: porovnaj dva prvky a prípadne ich vymeň. Spoznáš päť triediacich algoritmov, pri každom uvidíš ukážku v Pythone, dozvieš sa, prečo sú niektoré mnohonásobne rýchlejšie ako iné, a každý si môžeš pustiť krok za krokom.

Preskočiť na vizualizáciu triedenia ↓

Čo znamená utriediť údaje

Utriediť (zoradiť) údaje znamená usporiadať ich podľa zvoleného kľúča — čísla podľa veľkosti, mená podľa abecedy, súbory podľa dátumu. Pri vzostupnom triedení nasleduje po každom prvku rovnaký alebo väčší prvok, pri zostupnom rovnaký alebo menší. Na tejto stránke triedime celé čísla vzostupne.

Triedenie patrí k úlohám, ktoré počítače riešia najčastejšie:

• internetový obchod zoradí tovar podľa ceny, pošta správy podľa dátumu, tabuľkový editor riadky podľa zvoleného stĺpca,
• v utriedených údajoch sa dá veľmi rýchlo hľadať — pri binárnom vyhľadávaní stačí v milióne utriedených prvkov približne 20 porovnaní,
• po utriedení ľahko nájdeme najmenší a najväčší prvok, medián alebo opakujúce sa hodnoty, lebo rovnaké prvky stoja vedľa seba.

Údaje máme uložené v poli (v Pythone v zozname) s názvom a, ktoré má n prvkov. Prvky číslujeme od nuly: a[0], a[1], …, a[n - 1]. Číslu v hranatej zátvorke hovoríme index alebo pozícia prvku.

Porovnanie a výmena

Algoritmy na tejto stránke sa skladajú z dvoch základných operácií:

• porovnanie — zistíme, ktorý z dvoch prvkov je väčší, napríklad a[j] > a[j + 1],
• výmena — dva prvky si vymenia miesta, v Pythone a[i], a[j] = a[j], a[i].

Rýchlosť algoritmu preto nemeriame v sekundách, ktoré závisia od počítača, ale počtom porovnaní a výmen, ktoré urobí pri poli s n prvkami.

Stabilné triedenie a triedenie na mieste

Triedenie je stabilné, ak prvky s rovnakým kľúčom zostanú v pôvodnom vzájomnom poradí. Príklad: zoznam žiakov je zoradený podľa priezviska a my ho stabilne utriedime podľa triedy. Žiaci tej istej triedy potom zostanú zoradení podľa priezviska. Pri nestabilnom triedení by sa ich poradie mohlo pomiešať.

Algoritmus triedi na mieste (anglicky in-place), ak prvky presúva priamo v pôvodnom poli a okrem neho potrebuje len niekoľko pomocných premenných. Opakom je algoritmus, ktorý si vytvára pomocné pole — pri veľkých údajoch spotrebuje citeľne viac pamäte.

Bublinkové triedenie (bubble sort)

Myšlienka. Pole opakovane prechádzame zľava doprava a porovnávame susedné prvky. Ak sú v nesprávnom poradí, vymeníme ich. Veľké prvky tak postupne „vybublajú“ na koniec poľa.

Postup:

1. Porovnaj prvý a druhý prvok. Ak je ľavý väčší, vymeň ich.
2. Posuň sa o jedno miesto doprava a urob to isté. Pokračuj až po koniec neutriedenej časti. Po prvom prechode je najväčší prvok na konci poľa.
3. Prechod opakuj. Každý ďalší je o jedno porovnanie kratší, lebo prvky na konci sú už na svojom mieste.
4. Ak v celom prechode nenastala žiadna výmena, pole je utriedené a algoritmus skončí skôr.

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        vymena = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                vymena = True
        if not vymena:
            break
    return a

Počet porovnaní a výmen. Základná verzia bez kroku 4 urobí vždy (n − 1) + (n − 2) + … + 1 = n · (n − 1) / 2 porovnaní. So skorým ukončením stačí na už utriedené pole jediný prechod: n − 1 porovnaní a žiadna výmena. Najhorším prípadom je pole v obrátenom poradí, ktoré vyžaduje n · (n − 1) / 2 porovnaní a rovnako veľa výmen. Každá výmena opraví práve jednu dvojicu prvkov v nesprávnom poradí (inverziu), počet výmen sa preto rovná počtu inverzií v poli.

Kedy je vhodné. Je to najjednoduchší triediaci algoritmus, dobrý na pochopenie princípu a na veľmi malé alebo takmer utriedené polia. Na väčšie údaje je pomalý a v praxi sa nepoužíva. Je stabilný a triedi na mieste.

Triedenie výberom (selection sort)

Myšlienka. V neutriedenej časti poľa nájdeme najmenší prvok a vymeníme ho s prvým prvkom tejto časti. Utriedená časť na začiatku poľa tým narastie o jeden prvok.

Postup:

1. Polož i = 0. Prejdi pole od pozície i po koniec a zapamätaj si index m najmenšieho prvku.
2. Ak najmenší prvok nestojí na pozícii i, vymeň ho s prvkom na tejto pozícii.
3. Zväčši i o 1 a hľadaj minimum už len vo zvyšku poľa.
4. Po n − 1 prechodoch je pole utriedené — prvok, ktorý zostal posledný, je najväčší.

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        if m != i:
            a[i], a[m] = a[m], a[i]
    return a

Počet porovnaní a výmen. Pri hľadaní minima treba vždy prejsť celú neutriedenú časť, preto algoritmus urobí n · (n − 1) / 2 porovnaní pri každom vstupe — aj keď je pole už utriedené. Výmen je však najviac n − 1, v každom prechode najviac jedna. Bublinkové triedenie aj triedenie vkladaním ich v najhoršom prípade potrebujú až n · (n − 1) / 2.

Kedy je vhodné. Keď je výmena dvoch prvkov oveľa drahšia ako porovnanie, napríklad pri presúvaní veľkých záznamov. Inak je pomalé. Triedi na mieste, ale nie je stabilné: v poli 3_a, 3_b, 1 sa v prvom prechode vymení 1 s 3_a a vznikne 1, 3_b, 3_a — dve rovnaké trojky si vymenili poradie.

Triedenie vkladaním (insertion sort)

Myšlienka. Postupujeme ako pri ukladaní kariet do ruky. Ľavá časť poľa je utriedená a ďalší prvok do nej vložíme na správne miesto.

Postup:

1. Prvý prvok tvorí utriedenú časť.
2. Vezmi prvý prvok neutriedenej časti.
3. Kým je jeho ľavý sused väčší, vymeň ich. Prvok sa tak posúva doľava.
4. Keď narazí na menší alebo rovnaký prvok, prípadne na začiatok poľa, je vložený. Pokračuj ďalším prvkom.

def insertion_sort(a):
    for i in range(1, len(a)):
        j = i
        while j > 0 and a[j - 1] > a[j]:
            a[j - 1], a[j] = a[j], a[j - 1]
            j -= 1
    return a

V praxi sa vkladaný prvok najprv odloží do premennej a väčšie prvky sa iba posúvajú o jedno miesto doprava. Ušetrí sa tým časť zápisov do poľa, počet porovnaní zostáva rovnaký.

Počet porovnaní a výmen. Na už utriedenom poli stačí pri každom vkladanom prvku jedno porovnanie: spolu n − 1 porovnaní a žiadna výmena. V najhoršom prípade (obrátené poradie) musí každý prvok prejsť až na začiatok, čo dáva n · (n − 1) / 2 porovnaní aj výmen. Pri náhodne usporiadanom poli je to približne polovica. Počet výmen sa aj tu rovná počtu inverzií.

Kedy je vhodné. Na malé polia (niekoľko desiatok prvkov) a na takmer utriedené údaje, kde je veľmi rýchle. Preto ho na krátke úseky používajú aj knižničné triedenia. Je stabilné, triedi na mieste a dokáže spracúvať prvky, ktoré prichádzajú postupne.

Triedenie zlučovaním (merge sort)

Myšlienka. Používa princíp rozdeľuj a panuj. Pole rozdelíme na dve polovice, každú utriedime tým istým postupom (rekurzívne) a dve utriedené polovice zlúčime do jedného utriedeného poľa.

Postup:

1. Pole s jedným prvkom (alebo prázdne) je utriedené. Tu sa rekurzia zastaví.
2. Dlhšie pole rozdeľ na ľavú a pravú polovicu.
3. Každú polovicu utrieď rekurzívne.
4. Zlučovanie: porovnaj prvé (najmenšie) prvky oboch polovíc a menší z nich presuň do výsledku. Opakuj, kým sa jedna polovica neminie. Zvyšok druhej polovice pripoj na koniec.

def merge_sort(a):
    if len(a) <= 1:
        return a
    stred = len(a) // 2
    lava = merge_sort(a[:stred])
    prava = merge_sort(a[stred:])
    return zluc(lava, prava)

def zluc(lava, prava):
    vysledok = []
    i = j = 0
    while i < len(lava) and j < len(prava):
        if lava[i] <= prava[j]:
            vysledok.append(lava[i])
            i += 1
        else:
            vysledok.append(prava[j])
            j += 1
    vysledok.extend(lava[i:])
    vysledok.extend(prava[j:])
    return vysledok

Funkcia merge_sort pôvodné pole nemení, ale vráti nové, utriedené: a = merge_sort(a). Pri rovnosti berie funkcia zluc prvok z ľavej časti (podmienka <=), vďaka čomu je triedenie stabilné.

Počet porovnaní a zápisov. Prvky sa tu nevymieňajú, ale zapisujú do výsledku. Delením na polovice vznikne približne log₂ n úrovní a na každej z nich sa spolu zlúči všetkých n prvkov. Výsledkom je približne n · log₂ n zápisov a o niečo menej porovnaní — takmer nezávisle od toho, ako bol vstup usporiadaný.

Kedy je vhodné. Na veľké polia, keď potrebujeme zaručenú rýchlosť a stabilitu, a tiež na triedenie údajov, ktoré sa nezmestia do operačnej pamäte (zlučujú sa utriedené súbory). Nevýhodou je pomocná pamäť pre n prvkov — algoritmus netriedi na mieste.

Rýchle triedenie (quicksort)

Myšlienka. Aj rýchle triedenie pracuje podľa princípu rozdeľuj a panuj. Zvolíme jeden prvok, pivot, a úsek poľa preusporiadame tak, aby vľavo od pivota boli menšie prvky a vpravo väčšie alebo rovnaké. Pivot je tým na svojom konečnom mieste. Ľavú a pravú časť potom utriedime rovnakým postupom.

Preusporiadaniu okolo pivota hovoríme delenie (anglicky partition) a dá sa urobiť viacerými spôsobmi. Na tejto stránke používame Lomutovu schému delenia, v ktorej je pivotom posledný prvok úseku.

Postup:

1. Za pivot zvoľ posledný prvok úseku. Index i nastav na začiatok úseku — označuje miesto, kam príde najbližší prvok menší ako pivot.
2. Indexom j prejdi úsek od začiatku po predposledný prvok. Ak je a[j] menší ako pivot, vymeň a[i] s a[j] a zväčši i o 1.
3. Nakoniec vymeň pivot s prvkom a[i]. Pivot je na svojom konečnom mieste.
4. Rovnako utrieď úsek vľavo od pivota a úsek vpravo od neho. Úsek s najviac jedným prvkom je už utriedený.

def quick_sort(a, lavy, pravy):
    if lavy >= pravy:
        return
    pivot = a[pravy]
    i = lavy
    for j in range(lavy, pravy):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[pravy] = a[pravy], a[i]
    quick_sort(a, lavy, i - 1)
    quick_sort(a, i + 1, pravy)

Celé pole utriedime volaním quick_sort(a, 0, len(a) - 1). Ak v kroku 2 alebo 3 ukazujú oba indexy na ten istý prvok, výmena nič nezmení — takú výmenu do počtu nezarátavame.

Počet porovnaní a výmen. Delenie úseku s k prvkami potrebuje k − 1 porovnaní. Ak pivot delí úseky približne na polovice, vznikne asi log₂ n úrovní a porovnaní je rádovo n · log₂ n. V najhoršom prípade je pivot vždy najmenším alebo najväčším prvkom úseku. Úsek sa potom skráti len o jeden prvok a porovnaní je n · (n − 1) / 2. Pri Lomutovej schéme to nastane napríklad vtedy, keď je pole už utriedené alebo zoradené v obrátenom poradí.

Kedy je vhodné. V praxi patrí k najrýchlejším algoritmom na veľké polia v operačnej pamäti. Triedi na mieste, navyše potrebuje len pamäť na rekurziu. Nie je stabilné. Pred najhorším prípadom sa chráni lepšou voľbou pivota — vyberie sa napríklad náhodný prvok alebo prostredný z troch.

Riešené príklady

Vo všetkých príkladoch triedime to isté pole 5, 2, 8, 1, 9, 3. Rovnaké pole je prednastavené aj vo vizualizácii nižšie, takže si každý krok môžeš overiť. Zápis 5 > 2 ↔ znamená, že sme porovnali 5 a 2 a vymenili ich; pri zápise 5 ≤ 8 výmena nenastala.

Zložitosť: koľko práce triedenie stojí

Počet operácií závisí od počtu prvkov n. Pri bublinkovom triedení (v základnej verzii) aj pri triedení výberom sa v prvom prechode urobí n − 1 porovnaní, v druhom n − 2, v ďalšom zase o jedno menej, až napokon jediné. Sčítame ich ako členy aritmetickej postupnosti:

Pre n = 6 je to 5 + 4 + 3 + 2 + 1 = 15, čo sedí so vzorcom: 6 · 5 / 2 = 15.

Zápis O(n²) a O(n · log n)

Výraz n · (n − 1) / 2 sa dá upraviť na 0,5 · n² − 0,5 · n. Pri veľkom n rozhoduje člen s n², ostatné sú oproti nemu zanedbateľné. Preto hovoríme, že algoritmus má zložitosť O(n²) — čítame „rádovo n na druhú“. Znamená to: keď sa počet prvkov zdvojnásobí, práce je približne štyrikrát viac.

Triedenie zlučovaním a (v priemere) rýchle triedenie majú zložitosť O(n · log n). Logaritmus log₂ n udáva, koľkokrát treba n prvkov rozpoliť, aby zostal jediný; pre milión prvkov je to približne 20. Pri takomto algoritme znamená dvojnásobný počet prvkov len o niečo viac ako dvojnásobok práce.

Pri malom poli je rozdiel nepatrný, pri veľkom obrovský:

Počítač, ktorý stihne 100 miliónov porovnaní za sekundu, by milión prvkov triedil bublinkovým triedením približne 5 000 sekúnd, teda vyše 83 minút. Triedeniu zlučovaním by stačilo asi 0,2 sekundy.

Prehľad piatich algoritmov

Najlepší prípad O(n) pri bublinkovom triedení platí pre verziu so skorým ukončením. O(1) znamená stále rovnaké množstvo pamäte bez ohľadu na veľkosť poľa — algoritmus triedi na mieste. Rýchle triedenie potrebuje pamäť na rekurziu, v priemere O(log n).

V bežných programoch netreba triedenie písať nanovo. V Pythone slúži na triedenie vstavaná funkcia sorted(a) a metóda a.sort(). Používajú algoritmus Timsort, ktorý spája triedenie zlučovaním s triedením vkladaním, je stabilný a má zložitosť O(n · log n).

Pozri aj: anglický Sorting Algorithm Visualizer, ktorý má viac algoritmov a porovná dva vedľa seba, a tému Číselné sústavy.