DomJudge - Balenie¶

35 riešení

jazyk Počet Čas Znakov
C++ 2 0,05 s 2.261 - 3.743 B
Java 22 0,51 - 2,71 s 1.717 - 5.692 B
Python 11 0,56 - 0,81 s 998 - 2.553 B
  • Convex hull
  • Shoelace formula
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:

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
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:

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

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

image.png

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$
In [8]:
from random import randint
pole = [randint(10, 99) for _ in range(100)]
print(*pole)

18 98 90 27 13 99 11 29 36 88 15 95 33 43 54 15 36 47 86 29 62 13 69 22 19 81 87 28 20 20 22 13 99 42 32 30 12 95 85 13 98 46 78 24 21 35 79 95 52 46 66 37 67 29 48 89 35 86 19 31 19 90 38 52 68 51 85 80 32 12 41 84 15 56 49 13 62 19 42 83 87 94 34 31 83 17 16 75 52 25 50 28 64 66 65 97 72 11 77 10
In [3]:
!pip install more_itertools

Defaulting to user installation because normal site-packages is not writeable
Collecting more_itertools
  Downloading more_itertools-10.2.0-py3-none-any.whl (57 kB)
     -------------------------------------- 57.0/57.0 kB 199.0 kB/s eta 0:00:00
Installing collected packages: more_itertools
Successfully installed more_itertools-10.2.0
In [3]:
from  more_itertools import divide

children = divide(20, pole)
data = [list(c) for c in children]
In [7]:
zobraz_tabulku(data)
Out[7]:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 18 99 15 15 62 81 22 30 98 35 66 89 19 51 41 13 87 17 50 97
1 98 11 95 36 13 87 13 12 46 79 37 35 90 85 84 62 94 16 28 72
2 90 29 33 47 69 28 99 95 78 95 67 86 38 80 15 19 34 75 64 11
3 27 36 43 86 22 20 42 85 24 52 29 19 52 32 56 42 31 52 66 77
4 13 88 54 29 19 20 32 13 21 46 48 31 68 12 49 83 83 25 65 10
In [8]:
data_stl = [ sorted(stl) for stl in data]
zobraz_tabulku(data_stl, middle=True) #usporiadane stlpce
Out[8]:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 13 11 15 15 13 20 13 12 21 35 29 19 19 12 15 13 31 16 28 10
1 18 29 33 29 19 20 22 13 24 46 37 31 38 32 41 19 34 17 50 11
2 27 36 43 36 22 28 32 30 46 52 48 35 52 51 49 42 83 25 64 72
3 90 88 54 47 62 81 42 85 78 79 66 86 68 80 56 62 87 52 65 77
4 98 99 95 86 69 87 99 95 98 95 67 89 90 85 84 83 94 75 66 97
In [11]:
data_usp = sorted(data_stl, key=lambda x:x[2])
zobraz_tabulku(data_usp, middle=True) #usporiadane stlpce podla prostredneho riadku
Out[11]:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 13 16 13 20 12 13 19 11 15 13 15 21 29 15 12 35 19 28 10 31
1 19 17 18 20 13 22 31 29 29 19 33 24 37 41 32 46 38 50 11 34
2 22 25 27 28 30 32 35 36 36 42 43 46 48 49 51 52 52 64 72 83
3 62 52 90 81 85 42 86 88 47 62 54 78 66 56 80 79 68 65 77 87
4 69 75 98 87 95 99 89 99 86 83 95 98 67 84 85 95 90 66 97 94
In [13]:
zobraz_tabulku(data_usp, data_usp[len(data_usp)//2][2]) #zobrazi hodnoty podla pivota (prvku v strede)
Out[13]:
  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 13 16 13 20 12 13 19 11 15 13 15 21 29 15 12 35 19 28 10 31
1 19 17 18 20 13 22 31 29 29 19 33 24 37 41 32 46 38 50 11 34
2 22 25 27 28 30 32 35 36 36 42 43 46 48 49 51 52 52 64 72 83
3 62 52 90 81 85 42 86 88 47 62 54 78 66 56 80 79 68 65 77 87
4 69 75 98 87 95 99 89 99 86 83 95 98 67 84 85 95 90 66 97 94
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:

Ak hľadáme prvok, tak určite nemusíme prehľadávať "štvrtinu" tabuľky ... 3 riadky po $\frac{n}{10}$ stĺpcoch, teda $\frac{3.n}{10}$ vynecháme a prehľadávame rekurzívne zvyšok $0,7n$ .

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) $$

Celkovo lineárny čas ...

In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:

Usporiadanie známok¶

In [133]:
znamky = [1,2,3,2,1,3,1,2,4,2,1,5,2,3,2,1,1,2,3,4]
In [134]:
len(znamky)
Out[134]:
20
In [135]:
znamky.count(1)
Out[135]:
6
In [136]:
vysl = []
for znamka in range(1, 6):
    vysl.extend([znamka]*znamky.count(znamka)) #pridame prislusny pocet danej znamky
vysl
Out[136]:
[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.

In [ ]:
In [ ]:
In [ ]:
In [ ]:

Len jedným prechodom¶

In [6]:
from collections import Counter

Counter(znamky)
Out[6]:
Counter({1: 6, 2: 7, 3: 4, 4: 2, 5: 1})
In [8]:
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)$.

In [9]:
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]
Out[9]:
[1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5]
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:

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

In [138]:
hodnotenia = ['A', 'B', 'C', 'D', 'E', 'Fx']
znamky = ['A', 'B', 'C', 'A', 'Fx']
In [139]:
pocet = {} #slovnik, asociativne pole, mapa
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}
Out[139]:
['A', 'A', 'B', 'C', 'Fx']
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:

Reťazce¶

In [22]:
mena = ['Peter', 'Jan', 'Pavol', 'Peter', 'Jan']
In [163]:
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}
Out[163]:
['Jan', 'Jan', 'Pavol', 'Peter', 'Peter']
In [164]:
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})
Out[164]:
['Jan', 'Jan', 'Pavol', 'Peter', 'Peter']
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:

Známky osôb¶

In [93]:
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},
          ]
In [140]:
sorted(tabulka, key = lambda x : x['cas'])
Out[140]:
[{'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}]
In [119]:
sorted(tabulka, key = lambda x : x['zdrojak'])
Out[119]:
[{'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}]
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:

Usporiadanie počítaním (Counting Sort)¶

image.png

In [141]:
znamky = {'RKB': 1, 'JH': 2, 'PJS': 2, 'AB': 4, 'CD': 3, 'YY': 2, 'AZ': 2, 'UU' : 1, 'PA': 4}
In [146]:
count = [0 for _ in range(6)]
print(count)

[0, 0, 0, 0, 0, 0]
In [147]:
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]
In [148]:
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]
In [149]:
output = [None for _ in znamky]
print(output)

[None, None, None, None, None, None, None, None, None]
In [150]:
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

$O(n+k)$

In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:

Číslicové usporiadanie Radix Sort¶

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

614
369
340
795
140
669
438
976
252
474
In [ ]:
In [ ]:
In [ ]:
In [ ]:

  • 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
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:

Priehradkové usporiadanie Bucket Sort¶

In [153]:
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).

In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:

Ď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)

https://www.youtube.com/watch?v=InGeRuRk3f8 (The Perfect Sorting Algorithm?? Block Sort Explained (Wiki Sort, Grail Sort))

https://www.youtube.com/watch?v=h1Bi0granxM (Every Sorting Algorithm Explained in 120 minutes (full series))

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)