31. Triedenia

Triedením rozumieme taký algoritmus, ktorý usporiada vstupnú postupnosť prvkov (napr. pole, n-ticu, spájaný zoznam, …) tak, aby ich poradie zodpovedalo nejakému usporiadaniu, napr. vzostupne alebo zostupne. Prvky, ktoré takto usporadúvame, sa môžu skladať z viacerých zložiek (častí alebo atribútov), pričom len nejaká ich časť slúži na porovnávanie usporiadania - časti prvku, podľa ktorého usporadúvame, hovoríme kľúč.

Mnohé z týchto triediacich algoritmov sú in-place (triedenie na mieste), čo znamená, že výsledná usporiadaná postupnosť sa nachádza na tom istom mieste ako bola vstupná. Takýmto triedením je aj pythonovská metóda sort() pre typ pole (list), napr.

>>> pole = [7, 16, 3, 7, 9, 5, 10]
>>> pole.sort()
>>> pole
[3, 5, 7, 7, 9, 10, 16]

Iný typ triediacich algoritmov vstupnú postupnosť nemení, ale vytvorí novú usporiadanú postupnosť (najčastejšie v poli, t.j. typ list), ktorá obsahuje tie isté prvky, ako boli na vstupe, ale v správnom poradí. Napr. aj štandardná pythonovská funkcia sorted() pracuje na tomto princípe:

>>> pole = (7, 16, 3, 7, 9, 5, 10)
>>> pole1 = sorted(pole)
>>> pole1
[3, 5, 7, 7, 9, 10, 16]

V ďalších častiach ukážeme niekoľko najznámejších jednoduchých triediacich algoritmov. Zameriame sa len na in-place triedenia, t.j. také, ktoré triedia n-prvkové pole (typu list) a výsledok usporiadania bude na pôvodnom mieste.

Bubble_sort

Bublinkové triedenie postupne prechádza celé pole a porovnáva všetky vedľa seba ležiace dvojice prvkov: ak je prvý z nich väčší ako druhý, treba ich navzájom vymeniť. Tento postup sa opakuje dovtedy, kým nezostane celé pole utriedené, teda maximálne n-krát.

Zapíšme tento algoritmus:

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]

Všimnite si, že táto funkcia nevracia žiadnu hodnotu (teda vracia None) ani nič nevypisuje. Funkcia len modifikuje vstupné pole, ktoré dostala ako parameter.

Otestujme:

>>> pole = [7, 16, 3, 7, 9, 5, 10]
>>> bubble_sort(pole)
>>> pole
[3, 5, 7, 7, 9, 10, 16]

Skúsme si priebeh algoritmu vizualizovať tak, že vo vnútornom cykle ešte pred porovnaním vypíšeme obsah poľa a vyznačíme, ktoré dva prvky sa porovnávajú:

def bubble_sort(pole):
    for i in range(len(pole)):
        for j in range(len(pole)-1):
            print(*pole[:j], (pole[j], pole[j+1]), *pole[j+2:])   # pridali sme vypis
            if pole[j] > pole[j+1]:
                pole[j], pole[j+1] = pole[j+1], pole[j]

Po spustení rovnakého testu dostaneme dosť dlhý výpis, ale jeho začiatok je takýto:

(7, 16) 3 7 9 5 10
7 (16, 3) 7 9 5 10
7 3 (16, 7) 9 5 10
7 3 7 (16, 9) 5 10
7 3 7 9 (16, 5) 10
7 3 7 9 5 (16, 10)
(7, 3) 7 9 5 10 16
3 (7, 7) 9 5 10 16
3 7 (7, 9) 5 10 16
3 7 7 (9, 5) 10 16
3 7 7 5 (9, 10) 16
3 7 7 5 9 (10, 16)
(3, 7) 7 5 9 10 16
...

Z tohto výpisu vidíme, že po prvom prechode algoritmu (po prvých šiestich riadkoch) sa maximálny prvok 16 dostáva na koniec poľa, teda na svoje cieľové miesto. Každý ďalší prechod porovnáva všetky susediace dvojice prvkov, teda bude zakaždým porovnávať aj predposledný s posledným - čo je zrejme zbytočné. Totiž po každom prechode sa dostáva na svoje miesto ďalší a ďalší prvok od konca, nielen posledný prvok po prvom prechode. Z tohto dôvodu sa zvykne vnútorný cyklus zakaždým skrátiť o jeden prvok od konca. Vhodnejším zápisom by bolo:

def bubble_sort(pole):
    for i in range(len(pole)):
        for j in range(len(pole)-1-i):         # skracujeme vnutorny cyklus zakazdym o 1
            print(*pole[:j], (pole[j], pole[j+1]), *pole[j+2:])
            if pole[j] > pole[j+1]:
                pole[j], pole[j+1] = pole[j+1], pole[j]

Bublinkové triedenie sa dá ešte rôzne vylepšovať, ale ak by sme ho testovali pre väčšie vstupné polia, zistili by sme, že je stále aj po vylepšeniach veľmi pomalé. Keďže chceme otestovať jeho rýchlosť, musíme ešte odstrániť kontrolnú tlač. Budeme pritom kontrolovať, či je výsledné pole správne usporiadané:

import time
import random

for n in 500, 1000, 2000, 4000, 8000:
    pole = [random.randrange(n) for i in range(n)]
    spole = sorted(pole)         # kontrolne utriedene pole
    tim = time.time()
    bubble_sort(pole)            # bublinkove triedenie
    tim = time.time() - tim
    print(n, pole == spole, round(tim, 3))

Výpis môže vyzerať napr. takto:

500 True 0.047
1000 True 0.208
2000 True 0.833
4000 True 3.409
8000 True 13.737

Zrejme pre ešte väčšie polia bude toto triedenie bežať nie niekoľko desiatok sekúnd, ale možno niekoľko minút, alebo aj hodín …

Min sort

Triedenie s výberom minimálneho prvku pracuje na tomto princípe:

  • nájde minimálny prvok a zaradí ho na začiatok poľa
  • opäť nájde ďalší minimálny prvok (prvý pritom z hľadania vynechá) a zaradí ho ako druhý prvok (za minimálny) - máme dva minimálne prvky na svojom mieste
  • opäť nájde ďalší minimálny prvok (prvé dva pritom vynechá) a zaradí ho ako tretí prvok (za oba minimálne) - máme tri minimálne prvky na svojom mieste
  • … takto sa to opakuje, kým sa nespracujú všetky prvky poľa

Zaraďovanie nájdeného minimálneho prvku na začiatok robíme obyčajnou výmenou dvoch prvkov poľa: vymeníme nájdené minimum s prvkom na pozícii, kam chceme minimum zaradiť. Uvedieme dve rôzne verzie tohto algoritmu, pričom prvá z nich minimum hľadá tak, že do i-teho prvku (sem má prísť minimum) postupne priraďuje všetky, ktoré sú od i-teho menšie:

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

Táto verzia sa veľmi podobá na bublinkové triedenie, ale v tomto prípade robí zbytočne veľa výmen. Častejšie sa používa druhá verzia, ktorá najprv nájde, kde sa v poli nachádza minimum (jeho index) a až potom jednou výmenou vymení i-ty prvok s minimálnym:

def min_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]

Ak by sme chceli nejako vidieť, ako tento algoritmus funguje, mohli by sme si vložiť kontrolnú tlač, napr.

def min_sort(pole):
    print(*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]
        print(*pole[:i], [pole[i]], *pole[i+1:])

pole = [7, 16, 3, 7, 9, 5, 10]
min_sort(pole)
print('vysledok =', pole)

A dostaneme takýto výpis:

7 16 3 7 9 5 10
[3] 16 7 7 9 5 10
3 [5] 7 7 9 16 10
3 5 [7] 7 9 16 10
3 5 7 [7] 9 16 10
3 5 7 7 [9] 16 10
3 5 7 7 9 [10] 16
vysledok = [3, 5, 7, 7, 9, 10, 16]

Každý ďalší riadok ukazuje obsah poľa po jednom prechode vonkajšieho cyklu, t.j. po zaradení i-teho najmenšieho na správne miesto: v prvom riadku je ešte netriedené pole, v druhom je jeho obsah po zaradení prvého minima na svoje miesto (číslo 3), v ďalšom riadku je zaradené už aj druhé číslo 5, atď. V poslednom riadku výpisu je utriedené celé pole.

31.1. Vizualizácia triedenia

Rôznych algoritmov triedenia je dosť veľa, ale na základe výpisov obsahu poľa sa zriedkavo dá zistiť, ako to funguje naozaj. Často sa používajú iné zobrazovania momentálneho obsahu poľa, napr. grafický, v ktorom sú rôzne veľké hodnoty zobrazené rôznou dĺžkou úsečiek. Napr. takto by sme mohli zobraziť nejaké 100-prvkové neutriedené pole:

_images/31_1.png

Počas práce algoritmu by sa pri každej výmene dvoch prvkov poľa mohli vymeniť aj nakreslené úsečky - zrejme namiesto fyzického vymieňania úsečiek im len zmeníme dĺžky podľa aktuálneho obsahu príslušných prvkov poľa.

Čo vlastne budeme potrebovať od vizualizovaného algoritmu triedenia:

  • hneď na začiatku sa celé pole vykreslí do grafickej plochy ako vedľa seba ležiace úsečky, pričom ich dĺžka zodpovedá príslušnému prvku poľa, napr. takto
def bubble_sort(pole):
    for i in range(len(pole)):
        canvas.create_line(3*i, 600, 3*i, 600-pole[i])
    ...
  • aby sa nám neskôr s týmito úsečkami dobre pracovalo (budeme im meniť dĺžku), pre každý prvok poľa si zapamätáme id nakresleného grafického objektu, teda
def bubble_sort(pole):
    id = [0] * len(pole)
    for i in range(len(pole)):
        id[i] = canvas.create_line(3*i, 600, 3*i, 600-pole[i])
    ...
  • potom musíme pri každej výmene zmeniť aj dĺžky príslušných úsečiek, teda
def bubble_sort(pole):
    ...
            if pole[j] > pole[j+1]:
                pole[j], pole[j+1] = pole[j+1], pole[j]
                canvas.coords(id[j], 3*j, 200, 3*j, 200-pole[j])
                canvas.coords(id[j+1], 3*(j+1), 200, 3*(j+1), 200-pole[j+1])

Takto sa ale stáva výsledný algoritmus veľmi neprehľadný a keď budeme chcieť podobne vizualizovať nejaký iný triediaci algoritmus, budeme aj do neho musieť robiť takéto zásahy.

Urobíme to inak:

  • vytvoríme si novú triedu VizualizovanePole, ktoré sa bude starať o zobrazovanie celého poľa pomocou rôzne dlhých úsečiek
  • každá zmena nejakej hodnoty v poli (napr. pole[j] = pole[j+1]) automaticky prekreslí príslušnú úsečku
  • každý algoritmus, ktorý bude namiesto obyčajného poľa (typ list) používať naše VizualizovanePole, bude automaticky zobrazovať priebeh triedenia, teda namiesto práce s prvkami poľa sa budú volať naše metódy, ktoré budú pracovať s naozajstným poľom, ale okrem toho budú kresliť rôzne dlhé úsečky
  • správne utriedené pole sa na záver objaví ako postupnosť úsečiek s rastúcimi dĺžkami

Trieda VizualizovanePole musí zabezpečiť:

  • pri inicializácii inštancie v metóde __init__() si zapamätá samotné pole vo svojom atribúte (self.pole) a vykreslí všetky úsečky do grafickej plochy
  • pri zisťovaní dĺžky len(pole) metóda __len__() vráti aktuálnu dĺžku poľa
  • pri zmene hodnoty prvku poľa pole[index] metóda __setitem__() zrealizuje túto zmenu v poli a tiež zmení dĺžku príslušnej úsečky
  • pri zisťovaní hodnoty prvku poľa pole[index] metóda __getitem__() vráti príslušnú hodnotu zo svojho atribútu

Zapíšeme prvú verziu tejto triedy, zatiaľ bez vizualizovania úsečkami (preto ju nazveme Pole namiesto VizualizovanePole):

class Pole:
    def __init__(self, pole):
        self.pole = pole
        # tu sa bude vykreslovat obsah pola pomocou useciek

    def __getitem__(self, index):
        return self.pole[index]

    def __len__(self):
        return len(self.pole)

    def __setitem__(self, index, hodnota):
        self.pole[index] = hodnota
        # tu sa zmeni dlzka prislusnej usecky s danym indexom

Zavoláme s touto triedou bubble_sort():

pole = [7, 16, 3, 7, 9, 5, 10]
print(pole)
a = Pole(pole)
bubble_sort(a)
print(pole)

Všimnite si, že do funkcie bubble_sort() sme ako parameter neposlali pole typu list, ale inštanciu a triedy Pole, ktorá „obalila“ (tzv. wrap) toto naše pole. Samotná funkcia bubble_sort() o tom vôbec nevie. Tento test vypíše najprv pôvodné pole a potom utriedené:

[7, 16, 3, 7, 9, 5, 10]
[3, 5, 7, 7, 9, 10, 16]

Do triedy Pole teraz pridáme kreslenie čiar:

  • inicializácia __init__() vytvorí grafickú plochu (canvas) a vykreslí všetky úsečky podľa hodnôt v poli - zároveň sa identifikačné čísla týchto čiar uložia do poľa self.id
  • metóda __setitem__(), pomocou ktorej sa mení obsah prvku poľa, prekreslí príslušnú úsečku podľa tejto novej hodnoty
  • premenujeme ju na VizualizovanePole
import tkinter

class VizualizovanePole:
    def __init__(self, pole):
        self.pole = pole
        self.canvas = tkinter.Canvas(width=800, height=600, bg='white')
        self.canvas.pack()
        self.dx = 780 / len(pole)
        self.id = [0] * len(pole)
        for i in range(len(pole)):
            self.id[i] = self.canvas.create_line(i*self.dx, 600, i*self.dx, 600-pole[i], width=3, fill='blue')

    def __getitem__(self, index):
        return self.pole[index]

    def __len__(self):
        return len(self.pole)

    def __setitem__(self, index, hodnota):
        self.pole[index] = hodnota
        self.canvas.coords(self.id[index], index*self.dx, 600, index*self.dx, 600-hodnota)
        self.canvas.update()
        # self.canvas.after(100)

Teraz už môžeme otestovať bublinkové triedenie aj s vizualizáciou náhodného 100-prvkového poľa:

import random

pole = [random.randrange(500) for i in range(100)]
bubble_sort(VizualizovanePole(pole))
print(pole)

Môžete postupne vidieť najprv náhodne vygenerované pole, potom priebežný stav počas triedenia (na konci poľa sa ukladajú maximálne prvky) a na záver utriedené pole:

_images/31_1.png _images/31_2.png _images/31_3.png

Otestujte takto aj min_sort().

Insert sort

Triedenie vkladaním pracuje na takomto princípe:

  • predpokladajme, že istá časť poľa na začiatku je už utriedená
  • počas triedenia sa najbližší ešte neutriedený prvok zaradí do utriedenej časti na svoje miesto a tým sa tento utriedený úsek predĺži o 1

Zapíšme algoritmus:

def insert_sort(pole):
    # print(*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
        # print(*pole[:i+1], '|', *pole[i+1:])

Ako to funguje:

  • v premennej i je hranica medzi utriedenými a neutriedenými časťami poľa
    • pri štarte predpokladáme, že prvý prvok je už jednoprvková utriedená časť a preto začíname od indexu 1 (teda druhým prvkom poľa)
  • v premennej prvok je hodnota nasledovného prvku poľa, ktorú budeme zaraďovať do utriedenej časti
  • v premennej j je index posledného prvku v utriedenej časti - tento prvok budeme porovnávať s prvok a kým sú tieto hodnoty väčšie ako prvok, budeme utriedenú časť rozhŕňať a premennú j zmenšovať
  • na záver sme v utriedenej časti dosiahli voľné miesto pre vkladaný prvok (v premennej prvok)

Výpisy, ktoré sú tu zakomentované, môžu pomôcť pochopiť, ako to funguje. Otestujeme (aj s výpismi):

pole = [7, 16, 3, 7, 9, 5, 10]
insert_sort(pole)
print('vysledok =', pole)
7 16 3 7 9 5 10
7 16 | 3 7 9 5 10
3 7 16 | 7 9 5 10
3 7 7 16 | 9 5 10
3 7 7 9 16 | 5 10
3 5 7 7 9 16 | 10
3 5 7 7 9 10 16 |
vysledok = [3, 5, 7, 7, 9, 10, 16]

Znak '|' slúži na oddelenie utriedenej a ešte neutriedenej časti poľa.

Vyskúšajte toto triedenie vizualizovať pomocou triedy VizualizovanePole.

Quick sort

Je to najznámejší algoritmus rýchleho triedenia, ktorý v roku 1959 vymyslel Tony Hoare.

Algoritmus využíva rekurziu. Popíšme zjednodušený princíp:

  • najprv zvolíme ľubovoľný prvok poľa ako tzv. pivot (pre jednoduchosť zvolíme prvý prvok poľa)
  • ďalej všetky zvyšné prvky rozdelíme na tri kopy: na prvky, ktoré sú menšie ako pivot, na prvky, ktoré sa rovnajú pivot a na všetky zvyšné
  • teraz rovnakým algoritmom (t.j. rekurzívnym volaním) utriedime dve kopy: kopu menších a kopu väčších a takto utriedené časti (spolu s kopou rovnakých) nakoniec spojíme do výsledného utriedeného poľa

Prvá verzia je rekurzívna funkcia, ktorá nemodifikuje svoj parameter, len vráti novo vytvorené pole, ktoré už bude teraz utriedené (zrejme tento algoritmus nie je in-place):

def quick_sort(pole):
    if len(pole) < 2:
        return pole
    pivot = pole[0]
    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)

Takéto riešenie nemôžeme vizualizovať v grafickej ploche našou triedou VizualizovanePole, keďže výsledok sa postupne zlepuje z veľkého množstva malých kúskov pomocných polí (my vieme vizualizovať len zmeny v pôvodnom poli). Jedine, čo môžeme otestovať je odmerať čas trvania triedenia pre rôzne veľké náhodné polia, tak ako sme to robili pri bublinkovom triedení:

import time
import random

for n in 10000, 20000, 40000, 80000, 160000, 320000, 640000, 1000000:
    pole = [random.randrange(n) for i in range(n)]
    spole = sorted(pole)         # kontrolne utriedene pole
    tim = time.time()
    pole1 = quick_sort(pole)
    tim = time.time() - tim
    print(n, pole1 == spole, round(tim, 3))

Testovanie začína s desaťtisíc prvkovým poľom a končí s milión prvkovým. Môžete dostať približne takéto výsledky:

10000 True 0.107
20000 True 0.117
40000 True 0.256
80000 True 0.563
160000 True 1.195
320000 True 2.611
640000 True 6.107
1000000 True 10.526

V porovnaní s rýchlosťou bublinkového triedenia sa dá pochopiť, prečo dostalo toto triedenie názov rýchle.

Ďalej sa zameriame na verziu, ktorá nebude používať pomocné polia, ale quick_sort() prebehne v samotnom poli:

  • na začiatku sa samotné pole (jeho časť od indexu z do indexu k) rozdelí na dve časti:
  • zvolí sa pivot (napr. prvý prvok poľa) a zvyšné prvky sa postupne rozdelia do ľavej časti poľa (pred pivot) a pravej (za pivot) podľa toho či sú menšie alebo väčšie ako pivot
  • v premennej index je pozícia pivot v takto upravenom poli (ešte neutriedenom) - uvedomte si, že pivot je už na svojom mieste (podobne ako boli minimálne prvky v min_sort() a maximálne prvky v bubble_sorte())
  • ďalej nasleduje rekurzívne volanie pre ľavú časť poľa pred pivot a pre pravú časť poľa za pivot

Táto druhá verzia je už in-place, t.j. nevytvára sa nové pole, ale triedi sa priamo to pole, ktoré je parametrom funkcie:

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 teraz pozicia pivota
            quick(z, index-1)
            quick(index+1, k)

    quick(0, len(pole)-1)

Otestujme to pomocou vizualizácie:

import random
pole = [random.randrange(500) for i in range(750)]
quick_sort(VizualizovanePole(pole))

Môžete postupne vidieť, ako sa najprv náhodne vygenerované pole rozdelilo podľa pivota na menšie a väčšie prvky, potom sa takto rekurzívne rozdelil aj prvý úsek a na poslednom zábere je už polovica poľa utriedená a triedi sa zvyšok poľa:

_images/31_4.png _images/31_5.png _images/31_6.png

Niekedy sa triedenia zvyknú vizualizovať nie pomocou úsečiek ale len pomocou jedného koncového bodu úsečky - takto na začiatku vidíme náhodne rozhádzané bodky, ktoré sa postupne zoskupujú. Opravíme triedu VizualizovanePole:

class VizualizovanePole:
    def __init__(self, pole):
        self.pole = pole
        self.canvas = tkinter.Canvas(width=800, height=600, bg='white')
        self.canvas.pack()
        self.dx = 780 / len(pole)
        self.id = [0] * len(pole)
        for i in range(len(pole)):
            self.id[i] = self.canvas.create_line(i*self.dx, 600-pole[i], i*self.dx, 601-pole[i], fill='blue')

    def __getitem__(self, index):
        return self.pole[index]

    def __len__(self):
        return len(self.pole)

    def __setitem__(self, index, hodnota):
        self.pole[index] = hodnota
        self.canvas.coords(self.id[index], index*self.dx, 600-hodnota, index*self.dx, 601-hodnota)
        self.canvas.update()

Po spustení vizualizácie vidíme:

_images/31_7.png _images/31_8.png _images/31_9.png _images/31_10.png

31.2. Štandardné triedenie v Pythone

štandardná funkcia sorted() triedi, napr.

  • postupnosť čísel, reťazcov
  • znakový reťazec
  • postupnosť n-tíc, napr. postupnosť súradníc
  • postupnosť dvojíc (kľúč, hodnota), ktorá vznikne z asociatívneho poľa pomocou pole.items()

Výsledkom je vždy pole (typ list). Ak pri volaní uvedieme ďalší parameter reverse=True, pole sa utriedi zostupne od najväčších hodnôt po najmenšie.

Pozrime túto ukážku:

>>> import random
>>> pole = [random.randrange(10000) for i in range(15)]
>>> pole
[1372, 6518, 7580, 9941, 9518, 3211, 8428, 7624, 35, 9341, 572, 6218, 3819, 8943, 8527]
>>> sorted(pole)
[35, 572, 1372, 3211, 3819, 6218, 6518, 7580, 7624, 8428, 8527, 8943, 9341, 9518, 9941]
>>> sorted(pole, reverse=True)
[9941, 9518, 9341, 8943, 8527, 8428, 7624, 7580, 6518, 6218, 3819, 3211, 1372, 572, 35]

Vidíme vzostupne aj zostupne utriedené náhodne vygenerované pole. Ak by sme dostali úlohu toto pole utriediť len podľa posledných dvoch cifier každého čísla, bolo by to ťažšie. Vyrobme si pomocnú funkciu a nové pole, ktoré obsahuje len tieto posledné cifry:

>>> def posledne2(x):
        return x % 100

>>> pole1 = [posledne2(p) for p in pole]
>>> pole1
[72, 18, 80, 41, 18, 11, 28, 24, 35, 41, 72, 18, 19, 43, 27]
>>> sorted(pole1)
[11, 18, 18, 18, 19, 24, 27, 28, 35, 41, 41, 43, 72, 72, 80]

Ak chceme teraz vrátiť pôvodné čísla k týmto dvom posledným cifrám, musíme si ich pamätať, najlepšie vo dvojici spolu s poslednými 2 ciframi:

>>> pole1 = [(posledne2(p),p) for p in pole]
>>> pole1
[(72, 1372), (18, 6518), (80, 7580), (41, 9941), (18, 9518), (11, 3211), (28, 8428),
 (24, 7624), (35, 35), (41, 9341), (72, 572), (18, 6218), (19, 3819), (43, 8943), (27, 8527)]
>>> pole2 = sorted(pole1)
>>> pole2
[(11, 3211), (18, 6218), (18, 6518), (18, 9518), (19, 3819), (24, 7624), (27, 8527),
 (28, 8428), (35, 35), (41, 9341), (41, 9941), (43, 8943), (72, 572), (72, 1372), (80, 7580)]

Už je to skoro hotové: z týchto utriedených dvojíc zoberieme len pôvodné čísla, t.j. zoberieme druhé prvky dvojíc:

>>> [p[1] for p in pole2]
[3211, 6218, 6518, 9518, 3819, 7624, 8527, 8428, 35, 9341, 9941, 8943, 572, 1372, 7580]

A máme naozaj to, čo sme na začiatku očakávali: utriedené pôvodné pole, ale triedime len podľa posledných dvoch cifier čísel v poli.

Štandardná funkcia sorted() má okrem parametra reverse ešte jeden, ktorý slúži práve na toto: zadáme funkciu, ktorá určí, ako sa bude triedenie pri porovnávaní pozerať na každý prvok poľa - podľa tohto sa pôvodné pole bude triediť. Takže, komplikovaný postup s vytváraním dvojíc môžeme zjednodušiť použitím parametra key:

>>> sorted(pole, key=posledne2)
[3211, 6518, 9518, 6218, 3819, 7624, 8527, 8428, 35, 9941, 9341, 8943, 1372, 572, 7580]
>>> sorted(pole, key=lambda x: x%100)
[3211, 6518, 9518, 6218, 3819, 7624, 8527, 8428, 35, 9941, 9341, 8943, 1372, 572, 7580]

Vidíme, že tu môžeme použiť aj konštrukciu lambda. Takže, keď zadáme parameter key, tak triedenie nebude porovnávať prvky poľa, ale prerobené prvky poľa zadanou funkciou, napr. posledne2.

Zamyslite sa, v akom poradí sa teraz utriedi toto isté pole:

>>> sorted(pole, key=str)
[1372, 3211, 35, 3819, 572, 6218, 6518, 7580, 7624, 8428, 8527, 8943, 9341, 9518, 9941]

Zhrňme použitie štandardnej funkcie sorted():

štandardná funkcia sorted()

Funkcia sorted() z prvkov ľubovoľnej postupnosti (napr. pole, n-tica, reťazec, súbor, …) vytvorí pole týchto hodnôt vo vzostupne usporiadanom poradí. Funkcia môže mať ešte tieto dva nepovinné parametre:

  • reverse=True spôsobí usporiadanie prvkov vo vzostupnom poradí (od najväčšieho po najmenšie)
  • key=funkcia, kde funkcia je buď meno existujúcej funkcie alebo lambda konštrukcia - táto funkcia musí byť definovaná pre jeden parameter - potom vzájomné porovnávanie dvoch prvkov pri usporadúvaní bude používať práve túto funkciu

Je dôležité, aby sa všetky triedené prvky dali navzájom porovnávať, napr. nemôžeme usporiadať pole, ktoré obsahuje čísla aj reťazce. Môžeme ich pomocou parametra key previesť na také hodnoty, ktoré porovnávať vieme.

Nasledujúce ukážky ilustrujú najmä použitie parametra key.

  • usporiadanie množiny mien (čo sú reťazce v tvare meno priezvisko) najprv podľa priezvisk, a ak sú dve priezviská rovnaké, tak podľa mien:
>>> m = {'Janko Hrasko', 'Eugen Suchon', 'Ludovit Stur', 'Andrej Sladkovic', 'Janko Stur'}
>>> sorted(m)
['Andrej Sladkovic', 'Eugen Suchon', 'Janko Hrasko', 'Janko Stur', 'Ludovit Stur']
>>> sorted(m, key=lambda x: x.split()[::-1])
['Janko Hrasko', 'Andrej Sladkovic', 'Janko Stur', 'Ludovit Stur', 'Eugen Suchon']
  • usporiadanie telefónneho zoznamu podľa telefónnych čísel, keďže zoznam je tu definovaný ako asociatívne pole, vytvoríme z neho najprv pole dvojíc (kľúč, hodnota):

    >>> tel = {'Betka':737373, 'Dusan':555444, 'Anka': 363636, 'Egon':210210,
    'Cyril': 911111, 'Gaba':123456, 'Fero':288288}
    >>> sorted(tel.items())
    [('Anka', 363636), ('Betka', 737373), ('Cyril', 911111), ('Dusan', 555444),
     ('Egon', 210210), ('Fero', 288288), ('Gaba', 123456)]
    >>> sorted(tel.items(), key=lambda x: x[1])
    [('Gaba', 123456), ('Egon', 210210), ('Fero', 288288), ('Anka', 363636),
     ('Dusan', 555444), ('Betka', 737373), ('Cyril', 911111)]
    
  • usporiadanie poľa reťazcov bez ohľadu na malé a veľké písmená:

    >>> pole = ('Prvy', 'DRUHY', 'druha', 'pRva', 'PRVE', 'druhI')
    >>> sorted(pole)
    ['DRUHY', 'PRVE', 'Prvy', 'druhI', 'druha', 'pRva']
    >>> sorted(pole, key=str.lower)
    ['druha', 'druhI', 'DRUHY', 'pRva', 'PRVE', 'Prvy']
    >>> sorted(pole, key=lambda s: s.lower())
    ['druha', 'druhI', 'DRUHY', 'pRva', 'PRVE', 'Prvy']
    

    všimnite si dva spôsoby použitia metódy lower()

  • usporiadanie poľa bodov v rovine (pole dvojíc (x, y)) podľa toho, ako sú vzdialené od bodu (0,0); predpokladáme, že máme danú funkciu vzd(x,y), ktorá vypočíta vzdialenosť bodu od počiatku:

    >>> def vzd(x, y):
            return (x**2 + y**2)**.5
    >>> from random import randint as ri
    >>> body = [(ri(-5,5),ri(-5,5)) for i in range(10)]
    >>> body
    [(-1, 5), (2, 3), (-1, 0), (-1, -2), (0, 1), (-4, 4), (-4, 4), (5, -1), (5, -2), (-5, 0)]
    >>> sorted(body, key=lambda b: vzd(*b))
    [(-1, 0), (0, 1), (-1, -2), (2, 3), (-5, 0), (-1, 5), (5, -1), (5, -2), (-4, 4), (-4, 4)]
    

    všimnite si, že tu sme nemohli priamo zapísať key=vzd, lebo táto funkcia očakáva 2 parametre a my máme triediť dvojice

  • v danom slove usporiadať znaky podľa abecedy:

    >>> slovo = 'krasokorculovanie'
    >>> ''.join(sorted(slovo))
    'aaceikklnooorrsuv'
    
  • v poli sa vyskytujú reťazce aj čísla, treba to nejako usporiadať:

    >>> pole = ['abc', 3.14, 'def', 2.71, 'ghi', 333, 'jkl', 22]
    >>> sorted(pole)
    
    TypeError: unorderable types: float() < str()
    >>> sorted(pole, key=str)
    [2.71, 22, 3.14, 333, 'abc', 'def', 'ghi', 'jkl']
    

31.3. Cvičenie

  1. Ručne bez počítača zistite, čo sa bude vypisovať:
  • bublinkové triedenie
def bubble_sort(pole):
    for i in range(len(pole)):
        for j in range(len(pole)-1-i):
            if pole[j] > pole[j+1]:
                pole[j], pole[j+1] = pole[j+1], pole[j]
        print(*pole)

pole = [13, 7, 11, 3, 5, 2]
bubble_sort(pole)
  • triedenie s výberom minimálneho prvku
def min_sort(pole):
    for i in range(len(pole)-1):
        for j in range(i+1, len(pole)):
            if pole[i] > pole[j]:
                pole[i], pole[j] = pole[j], pole[i]
        print(*pole)

pole = [13, 7, 11, 3, 5, 2]
min_sort(pole)
  • triedenie vkladaním
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
        print(*pole)

pole = [13, 7, 11, 3, 5, 2]
insert_sort(pole)
  1. Zistite, čo budú vypisovať predchádzajúce tri triedenia, ak vstupné pole bude utriedené, napr.
  • bublinkové triedenie
pole = [1, 3, 5, 7, 9]
bubble_sort(pole)
  • triedenie s výberom minimálneho prvku
pole = [1, 3, 5, 7, 9]
min_sort(pole)
  • triedenie vkladaním
pole = [1, 3, 5, 7, 9]
insert_sort(pole)
  1. Spojazdnite vizualizáciu testov a otestujte, ako sa triedi 300-prvkové náhodné pole pomocou bubble_sort(), insert_sort() a quick_sort().
  2. Vylepšite bubble_sort() tak, aby algoritmus mohol skončiť skôr, a to vtedy, keď je pole už utriedené, t.j. keď počas jedného prechodu triedenia nebola už žiadna výmena, ďalší prechod sa už neuskutoční
  • vylepšené bublinkové triedenie
def bubble_sort(pole):
    ...
  • otestujte, napr.
pole = [random.randrange(1000) for i in range(1000)]
spole = sorted(pole)
bubble_sort(pole)
print(pole == spole)
  1. Napíšte funkciu zisti(pole, vzost=True), ktorá zistí (vráti True alebo False), či je zadaná postupnosť hodnôt usporiadaná vzostupne. Vstupnú postupnosť neukladajte do žiadneho poľa. Uvedomte si, že by ste túto postupnosť nemali indexovať, lebo to môže byť napr. range() alebo otvorený súbor. Parameter vzost s hodnotou False označuje, že kontrolujeme, či je postupnosť usporiadaná zostupne. Vzostupné usporiadanie označuje, že pre žiadne dva susedné prvky poľa nie je prvý z nich väčší ako druhý.
  • malo by fungovať napr.
>>> zisti([1, 3, 3, 4])
True
>>> zisti(range(10))
True
>>> zisti(range(10), False)
False
  1. Zapíšte verziu min_sort_rev(pole), ktorá na princípe triedenia s výberom minimálneho prvku utriedi vstupné pole v opačnom poradí.
  • otestujte, napr.
pole = [random.randrange(1000) for i in range(1000)]
spole = sorted(pole, reverse=True)
min_sort_rev(pole)
print(pole == spole)
  1. Táto verzia triedenia vkladaním v niektorých situáciách vypíše momentálny obsah celého poľa.
  • ručne odtrasujte tento algoritmus a vypíšte tieto kontrolné výpisy:
def insert_sort1(pole):
    for i in range(1,len(pole)):
        j,t = i,pole[i]
        while j > 0 and pole[j-1] > t:
            pole[j] = pole[j-1]
            j -= 1
        if j < i:
            pole[j] = t
            print(*pole)

p = [5,9,4,3,6,10,1,8,2,7]
insert_sort1(p)
  1. Nasledovná verzia triedenia vsúvaním insert_sort2() namiesto priraďovania do prvkov poľa používa metódy pop() a insert().
  • vložte do tejto funkcie kontrolné výpisy tak, ako sme to robili na prednáške, a skontrolujte jej spôsob triedenia
def insert_sort2(pole):
    for i in range(1, len(pole)):
        prvok = pole.pop(i)
        j = i-1
        while j >= 0 and pole[j] > prvok:
            j -= 1
        pole.insert(j+1, prvok)
  • zamyslite sa, prečo pre túto verziu nebude fungovať vizualizácia pomocou VizualizovanePole
  • odmerajte rýchlosť tohto triedenia v porovnaní s verziou z prednášky, napr. sem vložte meranie času
n = 10000
pole = [random.randrange(n) for i in range(n)]
pole1 = pole[:]
insert_sort(pole)
insert_sort2(pole1)
print(pole == pole1)
  1. Ručne bez počítača odkrokujte
  • quick_sort() z prednášky:
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 teraz pozicia pivota
            print(*pole)                        # <== vypis
            quick(z, index-1)
            quick(index+1, k)
    print(*pole)                                # <== vypis
    quick(0, len(pole)-1)

pole = [32, 12, 66, 19, 75, 29, 50]
quick_sort(pole)
  • program vypíše 6 riadkov čísel, pričom posledné dva sú rovnaké
  1. Zapíšte tri funkcie utried1(veta), utried2(veta) a utried3(veta), ktoré nejako usporiadajú slová v danej vete. Využijete štandardnú funkciu sorted() a prípadne aj parametre reverse a key.
  • utried1() usporiada slová vo vete podľa abecedy
  • utried2() usporiada slová vo vete podľa abecedy ale zostupne
  • utried3() usporiada slová vo vete podľa dĺžky slov (najprv najkratšie) a až keď sú rovnako dlhé podľa abecedy
def utried1(veta):
    return ...

def utried2(veta):
    return ...

def utried3(veta):
    return ...
>>> utried1('kohutik jaraby nechod do zahrady')
'do jaraby kohutik nechod zahrady'
>>> utried2('kohutik jaraby nechod do zahrady')
'zahrady nechod kohutik jaraby do'
>>> utried3('jano ide z blavy do brna')
'z do ide brna jano blavy'

31.4. Domáce zadanie

Naprogramujte triedenie radix_sort, ktoré využije túto triedu:

class RadixSort:
    def __init__(self, pole, key=None):
        self.pole = pole
        ...

    def pocet(self):
        ...
        return 0

    def prechod(self, index):
        ...

    def rob(self):
        for i in range(self.pocet()):
            self.prechod(i)

def radix_sort(pole, key=None):
    RadixSort(pole, key).rob()

Princíp fungovania tohto in-place triedenia:

  • naša verzia triedenia bude triediť len celé čísla;
  • samotné triedenie je založené na pozícii jednotlivých cifier v triedených celých číslach;
  • keďže budeme triediť podľa cifier v 10-ovej sústave, pripravíme si 10, tzv. priehradiek (po anglicky bucket): v jednom prechode triedenia potom postupne prejdene všetky čísla triedeného poľa a každé z nich zaradíme do príslušnej priehradky; na konci každého prechodu sa potom všetky priehradky zhrnú (postupne od 0. až po 9. priehradku) do pôvodného poľa;
  • v prvom prechode sa z každého triedeného čísla zoberie posledná cifra a tá určí číslo priehradky, kam sa zaradí
  • v každom ďalšom prechode sa kontrolujú vyššie a vyššie cifry čísel, teda v 2. prechode predposledné, v 3. prechode predpredposledné, atď. až po maximálny počet cifier vo všetkých číslach
  • pomocou tohto triedenia môžeme triediť aj komplexnejšie údaje, v ktorých len nejaká jedna časť bude slúžiť na triedenie, tzv. kľúč, vtedy parameter key definuje funkciu, ktorá z danej hodnoty vytvorí kľúč; fungovať by to malo podobne ako štandardná funkcia sorted(pole, key=funkcia)

Ukážme to na príklade:

  • ideme triediť toto pole:
170, 45, 75, 90, 802, 2, 24, 66
  • v 1. prechode presunieme všetky čísla do 10 priehradiek podľa poslednej cifry:
0: [170, 90]
1: []
2: [802, 2]
3: []
4: [24]
5: [45, 75]
6: [66]
7: []
8: []
9: []
  • teraz zhrnieme všetky priehradky do pôvodného poľa:
170, 90, 802, 2, 24, 45, 75, 66
  • v druhom prechode roztrieďujeme čísla podľa predposledných cifier (uvádzame len neprázdne priehradky):
0: [802, 2]
2: [24]
4: [45]
6: [66]
7: [170, 75]
9: [90]
  • opäť zhrnieme do jednej postupnosti:
802, 2, 24, 45, 66, 170, 75, 90
  • v poslednom prechode sledujeme len prvé cifry:
0: [2, 24, 45, 66, 75, 90]
1: [170]
8: [802]
  • po zhrnutí dostávame utriedené celé pole:
2, 24, 45, 66, 75, 90, 170, 802

Metódy triedy RadixSort by mali mať túto funkčnosť:

  • metóda pocet() vráti maximálny počet cifier všetkých čísel v poli; toto číslo sa využíva na výpočet počtu prechodov triedenia (v metóde rob)
  • metóda prechod(index) realizuje jeden prechod triedenia: najprv porozdeľuje všetky prvky poľa do príslušných priečinkov a potom ich naspäť presunie do pôvodného poľa (self.pole); parameter index určuje, o ktorý prechod sa jedná, t.j. pre index=0 algoritmus vykoná prvý prechod s poslednými ciframi čísel;
  • metóda rob() zavolá metódy pocet() a prechod() a pomocou nich utriedi celé pole

Funkcia radix_sort() obalí triedu Radix_sort. Metódu rob() ani radix_sort() nemá zmysel modifikovať - testovač bude využívať túto verziu funkcií.

Ak sa uvedie aj parameter key, všetky metódy pocet() aj prechod() s tým musia počítať, rovnako ako pre štandardný sorted().

Obmedzenia

  • vaše riešenie odovzdajte v súbore uloha8.py, pričom sa v ňom bude nachádzať len jedna definícia triedy RadixSort a jedna globálna funkcia radix_sort().

  • prvé dva riadky tohto súboru budú obsahovať:

    # autor: Janko Hrasko
    # uloha: 8. domace zadanie radix_sort
    
  • zrejme ako autora uvediete svoje meno

  • atribút pole v triede RadixSort musí obsahovať aktuálne triedené pole (typu list)

  • váš program by nemal počas testovania testovačom nič vypisovať (žiadne vaše testovacie print())

Testovanie

Keď budete spúšťať vaše riešenie na svojom počítači, môžete do súboru uloha8.py pridať testovacie riadky, ktoré ale testovač vidieť nebude, napr.:

if __name__ == '__main__':
    pole = [170, 45, 75, 90, 802, 2, 24, 66]
    r = RadixSort(pole)
    print('pocet =', r.pocet())
    for i in range(r.pocet()):
        r.prechod(i)
        print('prechod {}:'.format(i), pole)
    pole = [170, 45, 75, 90, 802, 2, 24, 66]
    r = RadixSort(pole, lambda x: x%100)
    print('pocet =', r.pocet())
    for i in range(r.pocet()):
        r.prechod(i)
        print('prechod {}:'.format(i), pole)

Tento test by vám mal vypísať:

pocet = 3
prechod 0: [170, 90, 802, 2, 24, 45, 75, 66]
prechod 1: [802, 2, 24, 45, 66, 170, 75, 90]
prechod 2: [2, 24, 45, 66, 75, 90, 170, 802]
pocet = 2
prechod 0: [170, 90, 802, 2, 24, 45, 75, 66]
prechod 1: [802, 2, 24, 45, 66, 170, 75, 90]