DomJudge - SuMin

• 10 riešení - 3 x Python, 1 x C++, 6 x Java

2.73 s C++

2.40 - 8.06 s Java

22.76 - 29.26 s Python

• suma môže presiahnuť 32 bitový int

Rýchle usporiadanie QuickSort

• pri správnom výbere pivota je $T(n) = 2.T\left(\frac{n}{2}\right)+O(n)$, teda $O(n \cdot \log n)$

• pri nesprávnom výbere to môže byť $T(n) = T(0)+T(n-1)+O(n)$, teda $O(n^2)$

• pri výber prvého alebo posledného prvku najhoršia možnosť nastáva v prípade, ak pole je už usporiadané

http://videolectures.net/mit6046jf05_leiserson_lec04/

• v praxi rôzne vylepšenia - medián z troch prvkov (prvý, prostredný a posledný), pri malom počte prvkov prepnúť na InsertSort, pri veľkom počte rekurzíí zase na MergeSort
• randomizovaný quicksort

Medián v lineárnom čase Median of medians/BFPRT

1973 Blum, Floyd, Pratt, Rivest, Tarján

Nájdenie $k$-teho najmenšieho prvku v poli (pre medián $k = \left\lfloor\frac{n}{2}\right\rfloor$)

• prvky zapíšeme do 5 riadkov
• každý stĺpec usporiadame (pre dôkaz zložitosti, v praxi stačí nájsť mediány)
• "usporiadame stĺpce" podľa prostredného riadku, vyberieme prostredný prvok z daného riadku (medián mediánov)
• podľa vybraného prvku pivotujeme pole ... teda zistíme jeho index
• ďalej pokračujeme v ľavej alebo v pravej časti podľa toho $k <?> index$

from random import randint
pole = [randint(10, 99) for _ in range(100)]
print(*pole)

21 91 26 39 56 35 58 28 26 58 75 87 75 95 39 98 21 39 69 59 92 10 27 53 39 53 65 38 28 91 28 81 51 36 31 37 14 73 57 38 65 87 31 47 77 45 68 30 84 30 26 66 21 74 77 24 41 32 80 42 32 79 76 85 80 45 74 79 86 38 33 58 49 91 99 66 33 73 57 81 74 56 43 21 91 87 11 65 62 76 55 23 62 25 65 13 21 43 83 26

from  more_itertools import divide

children = divide(20, pole)
data = [list(c) for c in children]

zobraz_tabulku(data)

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
0	21	35	75	98	92	53	28	37	65	45	26	24	32	45	33	66	74	87	55	13
1	91	58	87	21	10	65	81	14	87	68	66	41	79	74	58	33	56	11	23	21
2	26	28	75	39	27	38	51	73	31	30	21	32	76	79	49	73	43	65	62	43
3	39	26	95	69	53	28	36	57	47	84	74	80	85	86	91	57	21	62	25	83
4	56	58	39	59	39	91	31	38	77	30	77	42	80	38	99	81	91	76	65	26

data_stl = [ sorted(stl) for stl in data]
zobraz_tabulku(data_stl, middle=True) #usporiadane stlpce

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
0	21	26	39	21	10	28	28	14	31	30	21	24	32	38	33	33	21	11	23	13
1	26	28	75	39	27	38	31	37	47	30	26	32	76	45	49	57	43	62	25	21
2	39	35	75	59	39	53	36	38	65	45	66	41	79	74	58	66	56	65	55	26
3	56	58	87	69	53	65	51	57	77	68	74	42	80	79	91	73	74	76	62	43
4	91	58	95	98	92	91	81	73	87	84	77	80	85	86	99	81	91	87	65	83

data_usp = sorted(data_stl, key=lambda x:x[2])
zobraz_tabulku(data_usp, middle=True) #usporiadane stlpce podla prostredneho riadku

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
0	13	26	28	14	21	10	24	30	28	23	21	33	21	31	11	21	33	38	39	32
1	21	28	31	37	26	27	32	30	38	25	43	49	39	47	62	26	57	45	75	76
2	26	35	36	38	39	39	41	45	53	55	56	58	59	65	65	66	66	74	75	79
3	43	58	51	57	56	53	42	68	65	62	74	91	69	77	76	74	73	79	87	80
4	83	58	81	73	91	92	80	84	91	65	91	99	98	87	87	77	81	86	95	85

zobraz_tabulku(data_usp, data_usp[len(data_usp)//2][2]) #zobrazi hodnoty podla pivota (prvku v strede)

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
0	13	26	28	14	21	10	24	30	28	23	21	33	21	31	11	21	33	38	39	32
1	21	28	31	37	26	27	32	30	38	25	43	49	39	47	62	26	57	45	75	76
2	26	35	36	38	39	39	41	45	53	55	56	58	59	65	65	66	66	74	75	79
3	43	58	51	57	56	53	42	68	65	62	74	91	69	77	76	74	73	79	87	80
4	83	58	81	73	91	92	80	84	91	65	91	99	98	87	87	77	81	86	95	85

Ak hľadáme prvok, tak určite nemusíme prhľadávať "štvrtinu" tabuľky ... konkrétne 3 riadky a $\left\lceil\frac{n}{10} \right\rceil$ stĺpcov.

Krok	Zložitosť
prvky rozdelíme do 5-prvkových stĺpcov
každý stĺpec usporiadame (pre dôkaz zložitosti, v praxi stačí nájsť mediány)	$\frac{n}{5} \cdot O(1)$
"usporiadame stĺpce" podľa prostredného riadku, vyberieme prostredný prvok z daného riadku (medián mediánov)	$T\left(\frac{n}{5}\right)$
podľa vybraného prvku pivotujeme pole ... teda zistíme jeho $index$	$O(n)$
ďalej pokračujeme v ľavej alebo v pravej časti podľa toho, či $k \gtrless index$	$T\left(\frac{7n}{10}\right)$

$$ T(n)= \frac{n}{5} \cdot O(1)+T\left(\frac{n}{5}\right)+O(n)+T\left(\frac{7n}{10}\right)$$$$ T(n)= T\left(\frac{n}{5}\right)+T\left(\frac{7n}{10}\right)+O(n) $$

Usporiadanie známok

znamky = [1,2,3,2,1,3,1,2,4,2,1,5,2,3,2,1,1,2,3,4]

len(znamky)

20

znamky.count(1)

6

vysl = []
for znamka in range(1, 6):
    vysl.extend([znamka]*znamky.count(znamka)) #pridame prislusny pocet danej znamky
vysl

[1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5]

Zložitosť tohto algoritmu $O(n \cdot k)$, kde $k$ je rozsah hodnôt.

Len jedným prechodom

from collections import Counter

Counter(znamky)

Counter({1: 6, 2: 7, 3: 4, 4: 2, 5: 1})

pocet = [0 for i in range(0,6)]
for znamka in znamky:
    pocet[znamka] += 1
print(*pocet)

0 6 7 4 2 1

Vidíme, že časová zložitosť $O(n+k)$.

pocet = [0 for i in range(0,6)]
for znamka in znamky:
    pocet[znamka] += 1
print(pocet)
vysl = []
for znamka in range(1, 6):
    vysl.extend([znamka]*pocet[znamka]) #pridame prislusny pocet danej znamky
vysl

[0, 6, 7, 4, 2, 1]

[1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5]

Známky na VŠ - A, B, C, D, E, Fx

hodnotenia = ['A', 'B', 'C', 'D', 'E', 'Fx']
znamky = ['A', 'B', 'C', 'A', 'Fx']

pocet = {}
for h in hodnotenia:
    pocet[h] = 0
for znamka in znamky:
    pocet[znamka] += 1
print(pocet)
vysl = []
for znamka in hodnotenia:
    vysl.extend([znamka]*pocet[znamka]) #pridame prislusny pocet danej znamky
vysl

{'A': 2, 'B': 1, 'C': 1, 'D': 0, 'E': 0, 'Fx': 1}

['A', 'A', 'B', 'C', 'Fx']

Reťazce

mena = ['Peter', 'Jan', 'Pavol', 'Peter', 'Jan']

slovnik = {}
for meno in mena:
    if meno in slovnik:
        slovnik[meno] += 1
    else: #ak este nie je v zozname slov, tak musime zadefinovat
        slovnik[meno] = 1
print(slovnik)
vysl = []
for meno in sorted(pocetnost):#musime usporiadat kluce
    vysl.extend([meno]*pocetnost[meno]) #pridame prislusny pocet danej znamky
vysl

{'Peter': 2, 'Jan': 2, 'Pavol': 1}

['Jan', 'Jan', 'Pavol', 'Peter', 'Peter']

from collections import defaultdict

pocetnost = defaultdict(int) #defaultna hodnota je 0
for meno in mena:
    pocetnost[meno] += 1
print(pocetnost)
vysl = []
for meno in sorted(pocetnost):
    vysl.extend([meno]*pocetnost[meno]) #pridame prislusny pocet danej znamky
vysl

defaultdict(<class 'int'>, {'Peter': 2, 'Jan': 2, 'Pavol': 1})

['Jan', 'Jan', 'Pavol', 'Peter', 'Peter']

Známky osôb

znamky = {'RKB': 1, 'JH': 2, 'PJS': 2, 'AB': 4, 'CD': 3, 'YY': 2, 'AZ': 2, 'UU' : 1, 'PA': 4}

tabulka = [
    {'meno': 'BS', 'body' : 4, 'cas': 0.45, 'jazyk': 'py3', 'zdrojak': 718},
    {'meno': 'DD', 'body' : 4, 'cas': 1.86, 'jazyk': 'py3', 'zdrojak': 963},
    {'meno': 'DF', 'body' : 4, 'cas': 0.78, 'jazyk': 'java', 'zdrojak': 3246},
    {'meno': 'MP', 'body' : 4, 'cas': 2.60, 'jazyk': 'java', 'zdrojak': 2334},
    {'meno': 'SS', 'body' : 4, 'cas': 0.01, 'jazyk': 'cpp', 'zdrojak': 1790},
          ]

sorted(tabulka, key = lambda x : x['cas'])

[{'meno': 'SS', 'body': 4, 'cas': 0.01, 'jazyk': 'cpp', 'zdrojak': 1790},
 {'meno': 'BS', 'body': 4, 'cas': 0.45, 'jazyk': 'py3', 'zdrojak': 718},
 {'meno': 'DF', 'body': 4, 'cas': 0.78, 'jazyk': 'java', 'zdrojak': 3246},
 {'meno': 'DD', 'body': 4, 'cas': 1.86, 'jazyk': 'py3', 'zdrojak': 963},
 {'meno': 'MP', 'body': 4, 'cas': 2.6, 'jazyk': 'java', 'zdrojak': 2334}]

sorted(tabulka, key = lambda x : x['zdrojak'])

[{'meno': 'BS', 'body': 4, 'cas': 0.45, 'jazyk': 'py3', 'zdrojak': 718},
 {'meno': 'DD', 'body': 4, 'cas': 1.86, 'jazyk': 'py3', 'zdrojak': 963},
 {'meno': 'SS', 'body': 4, 'cas': 0.01, 'jazyk': 'cpp', 'zdrojak': 1790},
 {'meno': 'MP', 'body': 4, 'cas': 2.6, 'jazyk': 'java', 'zdrojak': 2334},
 {'meno': 'DF', 'body': 4, 'cas': 0.78, 'jazyk': 'java', 'zdrojak': 3246}]

Usporiadanie počítaním (Counting Sort)

znamky = {'RKB': 1, 'JH': 2, 'PJS': 2, 'AB': 4, 'CD': 3, 'YY': 2, 'AZ': 2, 'UU' : 1, 'PA': 4}

count = [0 for _ in range(6)]
print(count)

[0, 0, 0, 0, 0, 0]

print(znamky)
print(count)
for x in znamky:
    count[znamky[x]] += 1
print(count) # pocet hodnot = znamka

{'RKB': 1, 'JH': 2, 'PJS': 2, 'AB': 4, 'CD': 3, 'YY': 2, 'AZ': 2, 'UU': 1, 'PA': 4}
[0, 0, 0, 0, 0, 0]
[0, 2, 4, 1, 2, 0]

total = 0
for i in range(1, 6):
    count[i], total = total, count[i]+total
print(count) # pocet hodnot < znamka, t.j. prvy index, kde vo vysledku ma byt prvok s danou hodnotou

[0, 0, 2, 6, 7, 9]

output = [None for _ in znamky]
print(output)

[None, None, None, None, None, None, None, None, None]

for x in znamky:
    output[count[znamky[x]]] = x
    count[znamky[x]] += 1
    print(*count)
    print(*output)
    print()

0 1 2 6 7 9
RKB None None None None None None None None

0 1 3 6 7 9
RKB None JH None None None None None None

0 1 4 6 7 9
RKB None JH PJS None None None None None

0 1 4 6 8 9
RKB None JH PJS None None None AB None

0 1 4 7 8 9
RKB None JH PJS None None CD AB None

0 1 5 7 8 9
RKB None JH PJS YY None CD AB None

0 1 6 7 8 9
RKB None JH PJS YY AZ CD AB None

0 2 6 7 8 9
RKB UU JH PJS YY AZ CD AB None

0 2 6 7 9 9
RKB UU JH PJS YY AZ CD AB PA

Číslicové usporiadanie Radix Sort

from random import randint
for _ in range(10):
    print(randint(100, 999))

614
369
340
795
140
669
438
976
252
474

• usporiadanie podľa číslic (Counting Sort, kde $k=10$), od najmenej význajmej (Least Significant Digit) k najviac

    614  340   614  140
    369  140   438  252
    340  252   340  340
    795  614   140  369
    140  474   252  438
    669  795   369  474
    438  976   669  614
    976  438   474  669
    252  369   976  795
    474  669   795  976

Priehradkové usporiadanie Bucket Sort

for _ in range(10):
    print(randint(0, 99))

50
24
56
29
56
25
9
43
54
6

Rozdelíme na priehradky, napr.:

00-24: 24 9 6 ... delíme na 00-09, 10-19, 20-24
25-49: 29 25 43
50-74: 50 56 56 54
75-99: 

V niektorých prípadoch nám stačí spracovať prvé cifry (MSD) a vieme kde má byť v usporiadaní (teda nemusíme ani prečítať celé číslo).

Ďalšie algoritmy

https://en.wikipedia.org/wiki/Smoothsort

https://en.wikipedia.org/wiki/Library_sort

Algoritmy usporiadania

https://www.youtube.com/watch?v=GIvjJwzrHBU (Listening to Sorting Algorithms!)

https://www.youtube.com/watch?v=FNAUuYmkMPE (The Sorting Algorithm Olympics - Who is the Fastest of them All)

https://www.toptal.com/developers/sorting-algorithms (Sorting Algorithms Animations)

https://imgur.com/gallery/voutF (Sorting Algorithms Visualized)

https://sortvisualizer.com/ (Sort Visualizer)

Vlastnosti algoritmov usporiadania

• počet porovnaní = časová zložitosť v najhoršom prípade (najlepšom, priemernom)
• počet výmen
• "na mieste"/in-place ak pamäťová zložitosť je $O(\log n)$
• stabilita (prvky s rovnakou hodnotu zostanú v rovnakom poradí alebo nemusia)