7. Triedenia

S triedeniami sa stretáme už od prvého ročníka. Pri triedeniach si všímame rôzne kritériá, na základe ktorých môžeme usudzovať o ich kvalitách:

  • počet porovnaní - všetky doterajšie naše triedenia boli založené na porovnávaní prvkov
    • zložitosť týchto triedení je minimálne O(n log n) a maximálne O(n**2)
    • exitujú triedenia, ktoré nefungujú na princípe vzájomného porovnávania prvkov a ich zložitosť je O(n)
  • počet výmen - mnohé triedenia menia poradia prvkov vzájomným vymieňaním prvkov, v niektorých situáciách môže byť toto dosť dôležité kritérium
  • použitie pomocnej pamäte - koľko ďalšej pamäti je potrebný k danému algoritmu triedenia
    • niektoré algoritmy triedia priamo samotné pole, tzv. in-place, často potrebujú O(1) alebo O(log n) pomocnej pamäte
    • triedenia, ktoré nie sú in-place, vytvárajú utriedené nové pole a ich zložitosť je teda min. O(n)
  • rekurzia - už poznáme nerekurzívne triedenia (napr. bubble-sort), rekurzívne (napr. quick-sort) a zoznámime sa s takým, ktoré je rekurzívne aj nerekurzívne (merge-sort)
  • stabilita - vlastnosť stabilita označuje, že pre dva prvky poľa, ktoré majú rovnaký kľúč (pole[i].kluc==pole[j].kluc), ak bolo i<j tak aj po utriedení bude prvý prvok pred druhým (relatívna poloha rovnakých prvkov ostane po triedení zachovaná)
  • vnútorné/vonkajšie triedenia - či sa samotné triedenie aj pomocná pamäť nachádza v operačnej pamäti, alebo používame externú pamäť (napr. disk) - s týmto sa v tomto semestri nebudeme zaoberať

Pripomeňme si, čo už vieme o niektorých triedeniach z programovania v prvom ročníku, ale aj z niektorých prednášok v tomto predmete:

bubble_sort

Veľmi pomalé neefektívne in-place triedenie - použiteľné len pre malé polia.

n- krát prejde celé pole a zakaždým porovnáva všetky susedné prvky a prípadne ich navzájom vymení:

def bubble_sort(pole):
    for i in range(len(pole)):
        for j in range(len(pole)-1):
            if pole[j] > pole[j+1]:
                pole[j], pole[j+1] = pole[j+1], pole[j]

po každom prechode sa na koniec poľa presťahuje ďalšie maximum, teda po každom prechode je ďalší a ďalší prvok na svojom mieste, môžeme tento algoritmus trochu vylepšiť (vnorený cyklus bude zakaždým o 1 kratší), ale napriek tomu to bude stále O(n**2):

def bubble_sort(pole):
    for i in range(1, len(pole)):
        for j in range(len(pole)-i):
            if pole[j] > pole[j+1]:
                pole[j], pole[j+1] = pole[j+1], pole[j]

Ak vnútorný cyklus (jeden prechod triedenia) neurobí ani jednu výmenu, pole je už utriedené a môžeme okamžite ukončiť:

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

Vďaka tejto malej zmene najlepší prípad (pole už bolo utriedené), bude zložitosť len O(n) - toto je jedna z mála výhod bubble-sort - vie rozpoznať, že je pole utriedené. Počet výmen je tiež O(n**2).

Pamäťová zložitosť je O(1) - využíva len konštantný počet premenných, ich počet (veľkosť) nezávisí od veľkosti triedeného poľa.

selection_sort

in-sort - volali sme ho aj min_sort - najprv nájde v poli príslušné minimum a toto presťahuje niekde na začiatok:

def selection_sort(pole):
    for i in range(len(pole)-1):
        najmensi = i
        for j in range(i+1, len(pole)):
            if pole[najmensi] > pole[j]:
                najmensi = j
        pole[i], pole[najmensi] = pole[najmensi], pole[i]

Počet porovnaní je tu opäť O(n**2), počet výmen je len O(n), vhodný v prípadoch, keď sa pracuje s dátami, kde je výmena dvoch prvkov drahá operácia. Považuje sa za efektívnejší ako bubble-sort.

Stretli sme sa s ním aj pri prioritných frontoch, keď sme pomocou nich triedili. Realizácia UnsortedPriorityQueue triedila rovnako ako selection-sort.

insert_sort

in-place triedenie postupne vkladá na správne miesto do utriedenej časti všetky prvky poľa:

def insert_sort(pole):
    for i in range(1, len(pole)):
        prvok = pole[i]
        j = i-1
        while j >= 0 and pole[j] > prvok:
            pole[j+1] = pole[j]
            j -= 1
        pole[j+1] = prvok

Najprv je utriedenou časťou len 1. prvok, potom sa sem pridá na správne miesto 2. prvok, potom sa sem pridá 3. prvok, … Počet porovnaní je O(n**2). považuje sa za efektívnejší ako selection-sort. Jeho výhodou je to, že pre skoro utriedené polia má zložitosť skoro o(n).

Stretli sme sa s ním aj pri prioritných frontoch, keď sme pomocou nich triedili. Realizácia SortedPriorityQueue triedila rovnako ako insert-sort.

heap_sort

Stretli sme sa s ním pri HeapPriorityQueue:

  1. krok - heapify - pole sa prerobí na haldu - táto operácia má zložitosť O(n)
  2. krok - n-krát odoberieme minimálny prvok remove_min, ktorý zrejme uprace haldu operáciou hesp_down - keďže heap_down má zložitosť O(log n), n-krát to znamená zložitosť O(n log n)

Celková zložitosť algoritmu je O(n log n), je to in-place sort, ktorý nie je stabilný. Pamäťová zložitosť je O(1).

Rozdeľuj a panuj

Táto programátorská schéma (divide-and-conquer pattern) sa používa na riešenie mnohých algoritmických problémov. My si ju ukážeme na dvoch algoritmoch triedenia. Skladá sa z troch krokov:

  1. ak má úloha nejakú aspoň minimálnu veľkosť, rozdeľ ju na niekoľko disjunktných častí, inak vyrieš triviálny prípad (bez rekurzie)
  2. rekurzívne vyrieš úlohu pre každú z častí
  3. spoj tieto riešenia do výsledného celku

Merge sort

Rozdeľuj a panuj:

  1. ak má pole aspoň 2 prvky, rozdeľ ho na dve rovnaké časti (napr. veľkosti n//2 a n-n//2)
  2. rekurzívne zavolaj triedenie zvlášť pre každú z častí - dostaneme 2 utriedené časti celého poľa
  3. zlúč (merge) obe utriedené časti do výsledného poľa

Ideu rozdeľovania poľa na polovice vidíme (tzv. merge_sort strom):

_images/07_1.png

Toto bola 1. fáza algoritmu, keď sa pole rozdelilo na dve polovice a pre každú polovicu sa spustilo rekurzívne volanie, t.j. opäť rozdelenie na polovice. Toto pokračovalo dovtedy, kým bolo čo deliť, teda 1-prvkové pole sa už ďalej nedelilo.

Teraz prichádza fáza návratu z rekurzie, keď sa majú dve polovice poľa zlúčiť (tzv. merge) do utriedeného celku. Lenže vďaka rekurzii sa najprv budú zlučovať dve najvnorenejšie polovice, t.j. 1-prvkové polia: z nich sa vytvoria utriedené dvojprvkové:

_images/07_2.png

Na tomto obrázku vidíme princíp triedenia a nie skutočný algoritmus, lebo tu sme zrealizovali vynáranie z rekurzie naraz vo všetkých prípadoch, keď boli polia jednoprvkové. Pri ďalšom vynáraní sa z rekurzie opäť prebehne fáza zlučovania, keď sa z utriedených dvojprvkových polí vytvoria štvorprvkové:

_images/07_3.png

Takto to celé pokračuje, až kým sa postupne nezlúčia všetky polovice a teda nedostaneme výsledné utriedené pole:

_images/07_4.png

Zapíšeme tento rekurzívny algoritmus ako in-place triedenie, t.j. taká funkcia, ktorá modifikuje samotné pole a nevracia žiadnu hodnotu:

def merge_sort(pole):
    if len(pole) < 2:
        return
    stred = len(pole)//2
    pole1 = pole[:stred]
    pole2 = pole[stred:]
    merge_sort(pole1)
    merge_sort(pole2)
    # zlucovanie oboch casti do vysledneho pola:
    i = j = 0
    while i + j < len(pole):
        if j == len(pole2) or i < len(pole1) and pole1[i] < pole2[j]:
            pole[i+j] = pole1[i]
            i += 1
        else:
            pole[i+j] = pole2[j]
            j += 1

Zložitosť tohto triedenia je O(n log n), lebo rekurzia sa vnára log n krát a samotné zlučovanie má zložitosť O(n). Pekne je to vidieť aj na „merge_sort strome“: výška tohto stromu je naozaj dvojkový log n. Tiež vidíte, že v každej úrovni tohto strom sa nachádza presne n pôvodných prvkov, ktoré sú zoskupené do nejakých malých polí. Fáza zlučovania (merge) bude všetky tieto prvky (z malých polí) presúvať na správne miesta do dvojnásobne väčších polí. Keďže samotný cyklus „merge“ je while-cyklus, ktorý prejde toľko-krát koľko je spolu prvkov v dvoch malých poliach, tak spolu všetky-merge-cykly prejdú presne n krát.

Všimnite si, že sa tu veľmi intenzívne využívajú pomocné polia - odhadnite, aká je celková veľkosť všetkých pomocných polí, ktoré sa použijú počas vykonávania tohto algoritmu (opäť si môžete pomôcť „merge_sort stromom“).

Ak by sme netriedili pole, ale spájaný zoznam (napr. s metódami pre Zoznam: __len__(), pridaj_kon() a daj_prvy(), prvy(), …), mohli by sme výrazne ušetriť pomocnú pamäť: totiž namiesto pole1 a pole2 by sme mohli použiť pomocné zoznamy, ktoré by sa vytvorili prekopírovaním prvkov z pôvodného zoznamu najprv do prvého zoznamu a potom do druhého. Podobne by aj záverečné zlučovanie z týchto dvoch zoznamov vytvorilo jediný. Napr.

def merge_sort(zoznam):
    n = len(zoznam)
    if n < 2:
        return
    zoz1 = Zoznam()
    zoz2 = Zoznam()
    while len(zoz1) < n//2:
        zoz1.pridaj_kon(zoznam.daj_prvy())        # cita zo zaciatku zoznamu a pridava na koniec pomocneho
    while not zoznam.je_prazdny():
        zoz2.pridaj_kon(zoznam.daj_prvy())
    merge_sort(zoz1)
    merge_sort(zoz2)
    #zlucovanie oboch zoznamov do vysledneho
    while not zoz1.je_prazdny() and not zoz2.je_prazdny():      # kym su oba zoznamy neprazdne
        if zoz1.prvy() < zoz2.prvy():
            zoznam.pridaj_kon(zoz1.daj_prvy())
        else:
            zoznam.pridaj_kon(zoz2.daj_prvy())
    while not zoz1.je_prazdny():
        zoznam.pridaj_kon(zoz1.daj_prvy())
    while not zoz2.je_prazdny():
        zoznam.pridaj_kon(zoz2.daj_prvy())

Hoci sme tu ušetrili pomocnú pamäť, pravdepodobne toto riešenie stráca na rýchlosti kvôli manipuláciu s triedou Zoznam a jej metódami.

Nerekurzívny algoritmus zdola nahor

Užitočnou verziou merge sortu je nerekurzívny algoritmus zdola nahor. Opäť pozrieme na obrázok „merge_sort stromu“ a aj postup, ako sa postupne zlučovali najprv 1-prvkové polia na 2-prvkové, potom 2-prvkové na 4-prvkové, atď. Nakoniec sa takto dosiahlo utriedenie celého poľa. Presne tento postup využíva nerekurzívny algoritmus zdola nahor:

  1. porovnávaj dvojice susedných prvkov poľa: pole[0] a pole[1], pole[2] a pole[3], pole[4] a pole[5], …, keď v niektorej z dvojíc nie je dobré poradie (prvý nesmie byť väčší ako druhý), tak ich navzájom vymeň - takto dostávame utriedené malé dvojprvkové polia pole[0:2], pole[2:4], pole[4:6], …
  2. zober susedné dvojprvkové polia (sú už utriedené) a zlúč ich do 4-prvkových utriedených, t.j. zlúč pole[0:2], pole[2:4], potom pole[4:6], pole[6:8], … takto dostávame utriedené 4-prvkové úseky pole[0:4], pole[4:8], pole[8:12], …
  3. rob toto isté ale s väčším krokom k=4: zober susedné k -prvkové polia a zlúč ich do 2*k veľkých častí poľa - tento krok opakuj pre k = 2*k, kým platí, že k je menšie ako počet prvkov celého poľa

Keďže k sa tu stále zdvojnásobuje a cyklus končí pre k >= n (počet prvkov poľa), zrejme cyklus skončí po log n opakovaniach. Ak by sme mali pomocnú funkciu merge(a, b, c), ktorá zlúči úsek poľa v rozsahu range(a, b) s úsekom v range(b, c), mohli by sme zapísať:

def merge_sort(pole):
    def merge(a, b, c):
        # prvy usek range(a, b), druhy usek range(b, c)
        ...

    n = len(pole)
    k = 1
    while k < n:
        i = 0
        while i + k < n:
            merge(i, i+k, min(i+2*k, n))
            i += 2*k
        k += k

Podobnú ideu by sme vedeli zapísať aj pomocou spájaných zoznamov.

Quick sort

Toto triedenie poznáme z 1. ročníka (opäť je to princíp „rozdeľuj a panuj“):

  1. ak má pole aspoň 2 prvky, zvoľ hodnotu pivot a rozdeľ pole na časť menších ako pivot a väčších ako pivot
  2. rekurzívne zavolaj triedenie zvlášť pre každú z častí - dostaneme 2 utriedené časti celého poľa
  3. spoj obe utriedené časti do výsledného poľa

Ideu rozdeľovania poľa na dve časti podľa pivota vidíme:

_images/07_5.png

Pivota sme tu vybrali ako posledný prvok (je zakrúžkovaný). Rozdelené dve časti sú už bez tohto pivota (ten sa neskôr objaví vo výsledku v strede medzi nimi).

Toto bola 1. fáza algoritmu, keď sa pole rozdelilo na dve časti (menšie prvky ako pivot a väčšie prvky ako pivot) a pre každú časť sa spustilo rekurzívne volanie, t.j. opäť rozdelenie na dve časti. Toto pokračovalo dovtedy, kým bolo čo deliť, teda 1-prvkové (resp. prázdne) pole sa už ďalej nedelilo.

Teraz prichádza fáza návratu z rekurzie, keď sa majú obe časti spojiť do utriedeného celku (medzi ne sa zaradí pivot, ktorý sa v rekurzii netriedil). Vďaka rekurzii sa najprv budú spájať dvojice najvnorenejších častí:

_images/07_6.png

Opäť tento obrázok ukazuje princíp triedenia a nie skutočný algoritmus, lebo tu sme zrealizovali vynáranie z rekurzie naraz vo všetkých prípadoch, keď boli polia jednoprvkové. Pri ďalšom vynáraní sa z rekurzie opäť prebehne fáza spájania, keď sa z utriedených malých častí vytvoria väčšie (opäť sa medzi ne vkladá pivot):

_images/07_7.png

Takto to celé pokračuje, až kým sa postupne nespoja aj časti na najvyššej úrovni. Teda teraz dostávame výsledné utriedené pole:

_images/07_8.png

Zapíšme najprv rekurzívny algoritmus, ktorý ale nie je in-place, lebo nemodifikuje vstupné pole, ale vracia nové utriedené pole:

def quick_sort(pole):
    if len(pole) < 2:
        return pole
    pivot = pole[0]           # resp. pole[-1], alebo ina hodnota
    mensie = [prvok for prvok in pole if prvok < pivot]
    rovne = [prvok for prvok in pole if prvok == pivot]
    vacsie = [prvok for prvok in pole if prvok > pivot]
    return quick_sort(mensie) + rovne + quick_sort(vacsie)

Táto verzia quick sortu je veľmi prehľadná a môže slúžiť ako osnova rôznym iným verziám tohoto triedenia.

Známa (napr. z 1. ročníka) in-place verzia tohto triedenia:

def quick_sort(pole):
    def quick(z, k):
        if z < k:
            # rozdelenie na dve casti
            index = z
            pivot = pole[z]
            for i in range(z+1, k+1):
                if pole[i] < pivot:
                    index += 1
                    pole[index], pole[i] = pole[i], pole[index]
            pole[index], pole[z] = pole[z], pole[index]
            # v index je pozicia pivota
            quick(z, index-1)
            quick(index+1, k)

    quick(0, len(pole)-1)

Na internete nájdete veľa iných podobných verzií, ktoré realizujú in-place triedenie.

Podobne, ako sme vedeli upraviť merge sort pre triedenie spájaného zoznamu, môžeme to zapísať aj pre quick_sort:

def quick_sort(zoznam):
    if len(zoznam) < 2:
        return
    pivot = zoznam.prvy()
    mensie = Zoznam()
    rovne = Zoznam()
    vacsie = Zoznam()
    while not zoznam.je_prazdny():
        p = zoznam.daj_prvy()
        if p < pivot:
            mensie.pridaj_kon(p)
        elif p == pivot:
            rovne.pridaj_kon(p)
        else:
            vacsie.pridaj_kon(p)
    quick_sort(mensie)
    quick_sort(vacsie)
    while not mensie.je_prazdny():
        zoznam.pridaj_kon(mensie.daj_prvy())
    while not rovne.je_prazdny():
        zoznam.pridaj_kon(rovne.daj_prvy())
    while not vacsie.je_prazdny():
        zoznam.pridaj_kon(vacsie.daj_prvy())

Najväčším problémom quick sortu je jeho veľké riziko: najhorší prípad má kvadratickú zložitosť O(n**2). Toto nastane vtedy, keď pivot nerozdelí pole na dve časti, ale jedna z častí bude prázdna, napr. keď bolo už na začiatku pole utriedené a my vyberáme za pivota, napr. prvý prvok (alebo posledný). Zrejme v tomto prípade sú všetky zvyšné prvky väčšie ako pivot a teda prvá časť rozdelenia poľa na dve časti je prázdna a druhá obsahuje všetky prvky okrem pivota:

_images/07_9.png

Preto je snaha vyberať dobrého pivota, ktorý rozdelí pole na dve podobne veľké časti (nemusia byť rovnako veľké, len by nemala byť žiadna z nich prázdna - samozrejme toto je zaujímavé len pre väčšie polia, keď má pole napr. len 4 prvky, často bude jedna z častí prázdna). Stratégií výberu pivota je niekoľko a väčšina z nich je tak dobrá, že ich nemusíme ďalej riešiť, napr.

  • náhodný výber pivota (napr. pomocou random.choice())
  • priemer prvého a posledného prvku
  • priemer prvého, stredného a posledného prvku

Quick sort má výborný výkon (v porovnaní s inými triedeniami) a to hlavne pre veľké polia. Pre malé polia je tu už priveľká strata najmä s obhospodarením rekurzie a manipulácie s pivotmi. V tomto prípade sa využíva hybridný prístup: kým je pole veľké, postupuje sa štandardným quick sortom, ale keď sa príde už na malý úsek (napr. 50 prvkov), použije sa iné, možno „neefektívne“ triedenie, ktoré ale pre malé polia môže fungovať veľmi rýchlo - často sa v týchto prípadoch využíva napr. insert sort.

Bucket sort

Všetky triedenia, s ktorými sme sa zatiaľ stretli mali zložitosť buď O(n**2) alebo O(n log n). Dá sa ukázať, že triedenie, ktoré pracuje na princípe porovnávania hodnôt prvkov poľa, nemôže byť rýchlejšie ako O(n log n):

  • zjednodušená úvaha: máme nejaké triedenie, ktoré triedi n prvkové pole, uvažujme, že prvky sú navzájom rôzne

  • z triediaceho algoritmu si všímajme len operácie porovnávania dvoch prvkov pole[i] a pole[j] (napr. pole[i]<pole[j]), algoritmus sa pri týchto testoch rozhoduje, ako bude ďalej pokračovať, teda podľa odpovede „ano“ alebo „nie“

  • zakreslime tieto porovnávania aj s ďalším rozvetvovaním sa do binárneho stromu: prvé takéto porovnanie v algoritme bude v koreni stromu, tu sa to ďalej vetví na nejaké ďalšie dve porovnania (zrejme nejakých iných prvkov), atď.

  • keby sme zostavili kompletný strom takýchto rozvetvovaní pri porovnávaní dvojice prvkov poľa, zrejme v listoch takéhoto stromu (tu algoritmus skončil a teda pole už utriedil) budú všetky možné utriedenia n prvkového poľa a tých je n! (faktoriál)

  • takže máme binárny strom, ktorý má n! listov, otázkou je, aká minimálna môže byť výška takéhoto stromu (t.j. na minimálne koľko operácií porovnania vieme usporiadať prvky poľa), teda zaujíma nás odhad log n!

  • matematickými úpravami sa dá ukázať, že

    log n! > n log n
    
  • z tohto môžeme usudzovať, že žiadny algoritmus, ktorý triedi n prvkové pole porovnávaním dvojíc hodnôt, nemôže byť efektívnejší ako O(n log n)

Za istých podmienok, keď poznáme vlastnosti triedených hodnôt, vieme zostrojiť triedenie, ktoré má zložitosť napr. O(n). Predstavme si situáciu, že o triedených hodnotách (kľúčoch) vieme, že sú to celé čísla z intervalu <0, K-1>, teda K rôznych hodnôt. Na utriedenie takého poľa použijeme tzv. priehradkové triedenie (bucket sort):

  1. priprav K prázdnych priehradiek (napr. polia, alebo zoznamy)
  2. postupne prejdi všetky prvky vstupného poľa a na základe hodnoty (kľúča) ich zaraď na koniec príslušnej priehradky
  3. ak treba, ešte uprav (možno nejako usporiadaj) všetky priehradky
  4. spoj priehradky do výsledného poľa

Ak by sa v 3. kroku tieto priehradky ďalej rekurzívne triedili, mali by sme klasické rozdeľuj a panuj.

Dôležitou vlastnosťou tu je stabilita triedenia: ak majú dva prvky pole[i] a pole[j] rovnakú hodnotu (kľúč) a pritom i<j, tak v utriedenom výslednom poli sa bude pôvodná hodnota pole[i] nachádzať pred pole[j]. Niektoré verzie vyššie uvedených triedení boli stabilné (napr. bubble sort, insert sort, ale aj prvý quick sort, ktorý ešte nebol in-place), iné nie sú stabilné (napr. selection sort).

Pre bucket sort je stabilita dôležitá napr. vtedy, keď sa táto idea používa pre tzv. radix sort. Toto triedenie pracuje na princípe priehradiek, ale vychádza sa z toho, že triedená hodnota (kľúč) sa skladá z viacerých zložiek, pričom každá z nich má relatívne malý interval hodnôt. Napr. kľúčom je 6-ciferné číslo (číslo z intervalu 0 a 999999, zložkami sú cifry čísla), kľúčom je znakový reťazec ohraničenej veľkosti (napr. max. 10 znakov, zložkami sú znaky znakového reťazca), kľúčom je dvojica súradníc, z ktorých každá je z intervalu -100 a 100, atď.

  1. predpokladáme, že kľúč sa skladá z k zložiek (prípadne je doplnený nulovými hodnotami zľava alebo sprava podľa významu)
  2. priprav toľko priehradiek, koľko rôznych hodnôt má k -ta zložka kľúča (posledná cifra, posledný znak, …)
  3. postupne presuň všetky prvky poľa do príslušných priečinkov (vždy na koniec momentálneho obsahu) - rozhoduj sa len na základe k -tej zložky
  4. postupne spoj všetky neprázdne priečinky do jedného celku, prejdi na predposlednú zložku (k=k-1) a opakuj od 2. kroku
  5. keď prešiel tento postup pre všetky zložky, po poslednom spojení všetkých priečinkom máme utriedené celé pole

Jeden prechod tohto algoritmu má zložitosť O(n), lebo každý prvok sa najprv presunie na koniec nejakého priečinka (čo je O(1)), to je spolu O(n) a potom sa všetky priečinky spoja do jedného celku, čo nebude zložitejšie ako O(n). Keďže sa toto opakuje pre k krát pre všetky zložky, celková zložitosť radix sortu je O(k * n), pre malé k je to O(n)

Hľadanie prvku v poli

V praxi sa stretáme s úlohami, v ktorých máme nejaké n prvkové neutriedené pole a my potrebujeme čo najrýchlejšie nájsť v poradí k -ty najmenší (alebo najväčší) prvok poľa. Pre k=0 to znamená nájsť minimum, čo vieme urobiť so zložitosťou O(n). Podobne pre k=1 vieme nájsť druhé minimum na O(n), ale už je to trochu zložitejšie ako prvé minimum. Tiež pre k=n-1 je nájdenie maxima jednoduchá úloha so zložitosťou O(n). Ale ako je to vo všeobecnosti s nájdením k -teho najmenšieho prvku? Ak by sme použili nejaké rýchle triedenie, môžeme zapísať:

kty_prvok = sorted(pole)[k]

Zrejne takýto algoritmus má už zložitosť O(n log n).

Dá sa to ale aj rýchlejšie: jedna z možností je využiť ideu rekurzívneho quick sortu:

def select(pole, k):
    if len(pole) == 1:
        return pole[0]
    pivot = random.choice(pole)
    mensie = [prvok for prvok in pole if prvok < pivot]
    rovne = [prvok for prvok in pole if prvok == pivot]
    vacsie = [prvok for prvok in pole if prvok > pivot]
    # ak sa k nachadza v mensie (teda k < len(mensie)), rekurzivna volaj select(mensie, k)
    # inak ak sa k nachadza v rovne (teda k < len(mensie)+len(rovne)), return pivot
    # inak nachadza sa vo vacsie teda rekurzivne volaj select(vacsie, k-len(mensie)-len(rovne))

Tento algoritmus sa podobne ako quick sort rekurzívne vnára len do jednej z častí (mensie alebo vacsie), len do tej do ktorej patrí dané k. Zložitosť tohto algoritmu môžeme počítať podobne ako pri quick sorte, kde sme uvažovali s približne polovičným rozdelením poľa na dve časti. V prvom prechode treba prejsť všetky prvky poľa, aby sme ich rozdelili do príslušných pomocných polí, teda zložitosť je n. V druhom rekurzívnom volaní má pole približne polovicu, teda n/2. Každom ďalšom je to približne polovica z predchádzajúcej dĺžky. Toto skončí buď nájdením prvku (v časti rovne) alebo keď má celé pole dĺžku 1. Vieme zapísať celkový počet:

spolu = n + n/2 + n/4 + n/8 + ... + 1

Z matematiky vieme, že toto sa blíži k 2*n, teda celková zložitosť algoritmu select() je O(n).



Cvičenia

L.I.S.T.

selection-sort

  1. Navrhni také vstupné pole pre selection-sort, na ktorom ukážeš, že tento algoritmus nie je stabilné triedenie:

    def selection_sort(pole):
        for i in range(len(pole)-1):
            najmensi = i
            for j in range(i+1, len(pole)):
                if pole[najmensi] > pole[j]:
                    najmensi = j
            pole[i], pole[najmensi] = pole[najmensi], pole[i]
    

merge-sort

  1. Zapíš rekurzívny in-place algoritmus merge-sort (s pomocným poľom pri zlučovaní, daj pozor, aby bol stabilný), ktorý bude triediť dvojice (key, value) len podľa kľúča. Otestuj jeho rýchlosť a skontroluj správnosť utriedenia (pre rôzne veľké náhodné kľúče a hodnoty) v porovnaní so štandardným sorted().

  1. Zapíš nerekurzívny merge-sort zdola nahor a otestujte jeho rýchlosť v porovnaní s rekurzívnym algoritmom v úlohe (2). Dbajte pri tom, aby bolo aj toto triedenie stabilné.

quick-sort

  1. Uprav oba rekurzívne algoritmy quick-sort z prednášky tak, aby triedili dvojice (key, value) len podľa kľúča. Otestuj ich rýchlosť a korektnosť (pre rôzne veľké náhodné kľúče a hodnoty) v porovnaní so štandardným sorted(). Týmto otestuješ aj to, či sú to stabilné triedenia. V oboch algoritmoch zvoľ výber pivota rovnako.

  1. Pre prvý algoritmus quick-sort z prednášky, ktorý nie je in-place, nastav výber pivota ako stredný prvok poľa (pivot=pole[len(pole)//2]). Vygeneruj také testovacie 1000-prvkové pole, na ktorom tento algoritmus spadne (na pretečení rekurzie).

  1. Otestuj, ako sa zmení rýchlosť algoritmu quick-sort, ak sa bude úsek menší ako nejaké dané X triediť už len pomocou insert-sort (triviálny prípad rekurzie) - toto tredenie insert-sort uprav tak, aby triedilo len zadaný úsek poľa (a nie celé pole).
    • otestuj pre rôzne zvolenú veľkosť X, napr. 10, 50, 100, … a to pre to isté veľké náhodné pole

  1. Do algoritmu quick-sort pridaj ďalší parameter key, ktorý má rovnaký význam ako v štandardnej funkcii sorted(): týmto parametrom je funkcia, ktorá sa pri triedení aplikuje na každý prvok, aby sa zistilo, aká časť vstupu sa triedi. Napr.

    • keď chceme triediť dvojice hodnôt len podľa druhého prvku (napr. výška), zapíšeme:

      >>> pole = [('Dusan', 180), ('Elena', 166), ('Boris', 199), ('Zuza', 181)]
      >>> quick_sort(pole, key=lambda x: x[1])
      >>> pole
      [('Elena', 166), ('Dusan', 180), ('Zuza', 181), ('Boris', 199)]
      

  1. Zrealizuj algoritmus quick-sort bez rekurzie pomocou vlastného zásobníka:
    • do zásobníka treba ukladať dvojice (začiatok, koniec úseku)
    • algoritmus teda najprv rozhádže prvky poľa do dvoch úsekov (menšie ako pivot a väčšie ako pivot), potom hranice oboch týchto úsekov vloží do zásobníka a v cykle vyberie z vrchu zásobníka aktuálne spracovávaný úsek, spracuje ho a prípadne do zásobníka opäť vloží hranice úsekov, …
    • do zásobníka najprv vkladaj väčší z dvoch úsekov na triedenie a potom až menší z nich (zamysli sa prečo)

bucket-sort

  1. Vygeneruj n-prvkové náhodné pole dvojíc (key, value), kde key bude z intervalu <0, k) a value je ľubovoľná náhodná hodnota. Otestuj triedenie tohto poľa pomocou bucket-sortu pre rôzne hodnoty n a k: porovnaj čas triedenia a správnosť výsledku so štandardným triedením sorted(). Zabezpeč, aby bolo triedenie stabilné.

  1. Uprav predchádzajúce triedenie na radix-sort: v ktorom v každom prechode sa utriedi len jedna cifra z kľúča. T.j. v prvom prechode sa vytvorí 10 priehradiek a vstupné pole sa roztriedi podľa poslednej cifry; v druhom prechode sa pole roztriedi podľa predposlednej cifry, …

hľadanie k-teho najmenšieho prvku

  1. Naprogramuj rýchle hľadanie k-teho prvku v poli (typu list) úpravou algoritmu quick-sort

    • algoritmus:

      def select(pole, k):
          ...
      
    • ak je k mimo rozsah indexov poľa, funkcia vygeneruje chybu IndexError

    • funkciu otestuj na rýchlosť aj správnosť pre rôzne veľké polia



5. Domáce zadanie

L.I.S.T.

Triedenie tree_sort

Naprogramujte tree_sort. Ten funguje tak, že sa najprv vyrobí binárny vyhľadávací strom (BVS) a z neho sa pomocou inorder získa utriedená postupnosť. Binárny strom BVS sa ale vybuduje trochu inak:

  • namiesto reprezentácie vrcholov stromu, v ktorej všetky vrcholy obsahujú atribúty data, left, right, použijeme pre celý strom len dve n-prvkové polia (kde n je veľkosť poľa)
  • v koreni stromu je 0-ty prvok poľa
  • i-ty vrchol stromu popisuje i-ty prvok poľa, pričom ľavý syn (jeho index) je v left[i] a pravý je v right[i], koreň má ľavého syna v left[0] a pravého v right[0]
  • ak niektorý syn pre nejaký vrchol neexistuje, príslušný prvok poľa left, resp. right má hodnotu None
  • na vytvorenie BVS využite metódu insert(index), ktorá na správne miesto pridá ďalší vrchol - asi bude vhodné ju nedefinovať rekurzívne
  • keďže v poli sa niektorá hodnota môže nachádzať aj viackrát, v strome sa rovnaké prvky vkladajú do pravého podstromu, teda v ľavom podstrome sú všetky prvky menšie, v pravom sú väčšie alebo rovné

Po skonštruovaní stromu metódou insert(), teda po skonštruovaní dvoch polí left a right, algoritmus triedenia zavolá metódu inorder(), ktorá postupne vygeneruje utriedenú postupnosť prvkov pôvodného poľa. Metóda inorder() bude prvky poľa postupne vracať pomocou yield. Tiež bude vhodné ju nedefinovať rekurzívne, inak by mohla pre väčšie pole spadnúť na pretečení rekurzie.

Je zrejmé, že pôvodné triedené pole sa pri volaní tree_sort nesmie zmeniť. Okrem dvoch pomocných polí left a right nepoužívajte ďalšie pomocné polia. Zrejme si v inicializácii triedy BVS vytvoríte referenciu na pôvodné pole.

Použite tieto deklarácie:

class BVS:
    def __init__(self, pole):
        self.pole = pole
        self.left = ...
        self.right = ...
        ...

    def insert(self, index):
        ...

    def inorder(self, reverse=False):
        ...

def tree_sort(pole, reverse=False):
    tree = BVS(pole)
    for i in range(1, len(pole)):
        tree.insert(i)
    return tree.inorder(reverse)

kde

  • metóda insert(index): vloží do stromu prvok s daným indexom, teda v skutočnosti bude modifikovať len polia left a right;
  • metóda inorder(reverse): vráti ako generátor inorder-postupnosť prvkov poľa; parameter reverse (rovnako ako pre štandardnú funkciu sorted()) označuje, že metóda vygeneruje postupnosť v opačnom poradí prvkov
  • funkciu tree_sort() nemá zmysel modifikovať, lebo spúšťať sa bude táto pôvodná verzia

Váš program môžete testovať napr. takto:

if __name__ == '__main__':
    p = (27, 25, 34, 23, 25, 31, 28, 21)
    print(*tree_sort(p))
    print(*tree_sort(p, reverse=True))

Výpis potom bude:

21 23 25 25 27 28 31 34
34 31 28 27 25 25 23 21

V tomto prípade pre pole:

p = (27, 25, 34, 23, 25, 31, 28, 21)

vytvorená trieda BVS bude obsahovať tieto 2 pomocné polia:

left = [1, 3, 5, 7, None, 6, None, None]
right = [2, 4, None, None, None, None, None, None]

Toto označuje:

  • koreň (index 0) s hodnotou 27 má ľavého syna vrchol 1 (s hodnotou 25) a pravého syna vrchol 2 (s hodnotou 34)
  • vrchol na indexe 1 s hodnotou 25 má ľavého syna vrchol 3 (s hodnotou 23) a pravého syna vrchol 4 (s hodnotou 25)
  • všetky zvyšné vrcholy majú len ľavého syna
  • vrchol s indexom 2 (hodnota 34) má ľavého syna vrchol 5 (hodnota 31)
  • vrchol s indexom 3 (hodnota 23) má ľavého syna vrchol 7 (hodnota 21)

Z úlohového servera L.I.S.T. si stiahnite kostru programu riesenie5.py. Aby ste mohli spúšťať skúškové testy, program uložte do súboru riesenie5.py. Na začiatok súboru pridajte tieto tri komentárové riadky (s vašim menom a dátumom):

# 5. zadanie: tree_sort
# autor: Alan Turing
# datum: 16.11.2018

Riešenie odovzdajte na úlohový server L.I.S.T. najneskôr do 23:00 28. novembra. Môžete zaň získať 10 bodov.

© Copyright 2018-2019, Andrej Blaho.
Naposledy aktualizované 14. feb. 2019.
Vytvorené pomocou Sphinx 1.8.4.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.