Python
, 1 x C++
, 6 x Java
2.73 s C++
2.40 - 8.06 s Java
22.76 - 29.26 s Python
QuickSort
¶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/
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$)
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)$ |
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.
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]
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']
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']
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}]
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
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
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).
https://en.wikipedia.org/wiki/Smoothsort
https://en.wikipedia.org/wiki/Library_sort
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)