====== 5. Řazení a třídění, složitost ======
V Pythonu existuje vícero způsobů pro řazení/třídění složených datových typů. [[https://docs.python.org/3/howto/sorting.html|Základní]] jsou dvě metody:
- pomocí funkce [[https://docs.python.org/3/library/functions.html#sorted|sorted]]
- pomocí medoty [[https://docs.python.org/3/library/stdtypes.html#list.sort|list.sort()]]
==== Řazení listů ====
import random
import copy
# náhodné pořadí číslic 0-9
a = list(range(10)) # vytvori posloupnost 0 az 9 a pretypuje na seznam
random.shuffle(a) # nahodne prehazi posloupnost a
b = a
c = a.copy()
d = copy.deepcopy(a)
print('Original: {}'.format(a))
# řazení pomocí funkce sorted
a_sorted = sorted(a)
print('Sorted: {}'.format(a_sorted))
print('b (=): {}'.format(b))
print('c (copy): {}'.format(c))
print('d (deepcopy): {}'.format(d))
# řazení pomocí metody list.sort()
a.sort()
print('Sorted: {}'.format(a))
print('b (=): {}'.format(b))
print('c (copy): {}'.format(c))
print('d (deepcopy): {}'.format(d))
# POZOR - metoda list.sort() seřadí seznam na místě
# dojde tedy k přepisu původního seznamu
a = copy.deepcopy(d)
print('Original: {}'.format(a))
e = a.sort()
print('a after sort: {}'.format(a))
print('e: {}'.format(e))
a = ['Z', 'a', 'A' ,'z']
print(sorted(a))
# Proč je výsledek řazení takový jaký je?
# Velká písmena jsou před malými kvůli ASCII
a = ['Z', 'a', 'A' ,'z']
print([ord(znak) for znak in a]) # funkce ord() vypíše hodnotu ASCII pro daný znak
# pro zajímavost - funkce chr() vypíše znak podle hodnoty ASCII
=== List obsahující více datových typů ===
l = [7, 'foo', 'Whale', 'Foo', 'whale', '7', 'seven', [1, 2, 3]]
#l.sort() # Error
l.sort(key=str) # případně print(sorted(l, key=str))
print(l)
l = [7, 'foo', 'Whale', 'Foo', 'whale', '7', 'seven', [1, 2, 3]]
print(sorted(l, key=lambda x: str(x).lower()))
print(sorted(l, key=lambda x: len(str(x))))
print(sorted(l, key=lambda x: str(x)[1] if len(str(x))>1 else str(x)[0]))
==== Řazení ostatních složených datových typů ====
a = list(range(10))
random.shuffle(a)
b = tuple(a.copy())
c = 'qwertyuipolkjhgfdsazxcvbnm'
temp = [c[random.randint(0,len(a)-1)] for element in range(len(a))]
d = dict(zip(temp, a))
e = set(a)
f = [[y+random.randint(-5,5) for y in a.copy()] for k in range(3)]
print('Original list: {}'.format(a))
print('Original tuple: {}'.format(b))
print('Original string: {}'.format(c))
print('Original dictionary: {}'.format(d))
print('Original set: {}'.format(e))
print('Original 2D list: {}'.format(f))
# Test metody list.sort()
print(b.sort()) # místo b zkuste zadat c, d, e, f (kontrola funkčnosti pro jednotlivé typy)
var_to_sort = copy.deepcopy(f) # místo b zkuste zadat c, d, e (kontrola funkčnosti pro jednotlivé typy)
g = sorted(var_to_sort)
print('Original: {}'.format(var_to_sort))
print('Sorted: {}'.format(g))
# Pro zajímavost, řazení slovníku podle hodnoty (místo řazení podle klíče)
var_to_sort = copy.deepcopy(b)
g = sorted(var_to_sort, key=lambda item: var_to_sort[item])
print('Original: {}'.format(var_to_sort))
print('Sorted: {}'.format(g))
===== Vyhledávací algoritmy =====
Co kdybychom si vyhledávací/řadicí algoritmus chtěli naprogramovat sami, bez použití již zabudovaných funkcí/metod.
//(Počítáme s tím, že pokud se v následujících cvičeních setkáte s řazením, využijete k tomuto výkonu jednu ze zabudovaných metod. Tato sekce je spíše pro pochopení jednotlivých algoritmů.)//
----
**Animace řadicích algoritmů**
Na ose x je současná pozice prvku, na ose y pak velikost prvku.
Bubble sort, insertion sort, merge sort, odd even sort, quick sort
# Definujeme si nejprve funkci, která nám vrátí neseřazený list hodnot v rozmezí -100 až 100
def get_unsorted(length=100):
"""
Unsorted array of integers.
Args:
length (int): Number of elements in the returned array. *Default: 100.*
Returns:
list[int]: An array full of random integers ranging from -100 to 100 (100 not included).
"""
return [random.randrange(-100, 100) for i in range(length)]
# Zkouška zda výše zmíněná funkce funguje podle očekávání
print(get_unsorted(10))
=== Bubble sort ===
Čísla tzv. probublávají.
* Jeden cyklus:
* Vezmeme $[x]$ a $[x+1]$ hodnotu, kde $x$ značí pozici (začínáme s $x = 1$)
* Hodnoty porovnáme. Pokud platí $[x]$ > $[x+1]$, vyměníme pozice obou hodnot.
* Posuneme se na porovnání dalších hodnot (tedy $x = x+1$)
* Největší hodnota probublá nakonec
* Složitost:
* Při každém cyklu dojde k zařazení alespoň jedné hodnoty.
* Pro $n$ prvků je tedy potřeba $n-1$ cyklů
* V každém cyklu dochází maximálně k $n-1$ porovnání
* Složitost algoritmu je tedy $\mathcal{O}(n^2)$ (v nejlepším případě $\mathcal{O}(n)$, pro jeden cyklus)
== Úloha 1. - Implementuj Bubble sort ==
a = get_unsorted(10)
b = copy.deepcopy(a)
def bubble_sort(a):
#
bubble_sort(a)
print(a)
print(sorted(b))
=== Insert(-ion) sort ===
V prvním cyklu se nic nestane, jelikož bereme v úvahu pole/seznam o velikosti jednoho prvku.
* n-tý cyklus (n>1):
* Zvětšíme hledanou velikost seznamu o jeden (nový) prvek.
* Tento nový prvek zařadíme na správné místo v daném seznamu
* Postupně porovnáváme nový prvek se současnými prvky v daném (pod-)seznamu, a to od zadu
* Je-li nový prvek větší než druhý prvek v porovnání, jednotlivé prvky prohodíme
* V okamžiku kdy není nový prvek větší než druhý prvek v porovnání, dojde k ukončení daného cyklu
* Zvětšíme hledanou velikost seznamu o další (nový) prvek
* Složitost:
* Při každém cyklu dojde k zařazení alespoň jedné hodnoty.
* Pro $n$ prvků je tedy potřeba $n-1$ cyklů
* V každém cyklu dochází maximálně k $n-1$ porovnání
* Složitost algoritmu je tedy $\mathcal{O}(n^2)$ (v nejlepším případě $\mathcal{O}(n)$, pro jeden cyklus)
a = get_unsorted()
def insertion_sort(a):
""" sorts array a in-place in ascending order"""
for i in range(1,len(a)): # a[0:i] is sorted
val=a[i]
j=i
while j>0 and a[j-1]>val:
a[j]=a[j-1]
j-=1
a[j]=val
return a
insertion_sort(a)
print(a)
=== Select(-ion) sort ===
* Jeden cyklus:
* Snažíme se najít a správně zařadit $i$-tý nejmenší prvek na pozici $x[i]$ v daném seznamu
* Seznam můžeme rozdělit na seřazenou a neseřazenou část
* Najdeme nejmenší prvek v neseřazené části (postupným porovnáváním prvků)
* Nejmenší prvek v neseřazené části zařadíme na první pozici v neseřazené části seznamu
* První prvek v neseřazené části zahrneme nakonec seřazené části
* Neseřazenou část zmenšíme o první prvek zleva (změnšíme vyhledávací oblast)
* Složitost:
* Při každém cyklu dojde k zařazení alespoň jedné hodnoty.
* Pro $n$ prvků je tedy potřeba $n-1$ cyklů
* V každém cyklu dochází maximálně k $n-1$ porovnání
* Složitost algoritmu je tedy $\mathcal{O}(n^2)$
== Úloha 2. - Implementuj Select(-ion) sort ==
a = get_unsorted(10)
b = copy.deepcopy(a)
def selection_sort(a):
#
selection_sort(a)
print(a)
print(sorted(b))
=== Ukázka dalších řadicích algoritmů ===
from cv05_modul import heap_sort
a = get_unsorted()
print(heap_sort(a))
from cv05_modul import merge_sort
a = get_unsorted()
print(merge_sort(a))
=== Rychlost jednotlivých řadicích algoritmů ===
def test_sort(f=bubble_sort, repeats=100, length=100):
for j in range(repeats):
a=[random.randrange(100000) for i in range(length)]
if f.__name__ == 'sorted':
a = f(a)
else:
f(a)
for i in range(length-1):
assert(a[i]<=a[i+1])
# assert vrátí chybu v případě, že je == False
# podobně jako:
# if not : raise AssertionError()
print(f.__name__,"sort test passed")
== Využití tzv. Magic funkce ==
Magic funkce jsou součástí IPythonu ([[https://ipython.readthedocs.io/en/stable/interactive/magics.html|seznam dostupných Magic funkcí]]).
%whos
%time test_sort(f=bubble_sort, repeats=50, length=1000)
=== Úloha 3. - Seřaď lichá čísla ===
Napište funkci ''%%sort_odd%%'', která seřadí lichá čísla vstupního sezname, avšak sudá čísla nechá být.
Příklad:
[3, 2, 1, 0] => [1, 2, 3, 0] [2, 5, 3, 7, 6, 0, 1, 9, 4, 8] => [2, 1, 3, 5, 6, 0, 7, 9, 4, 8]
[-4, -1, -3, -2, -5] => [-4, -5, -3, -2, -1] [-8, -5, -7, -9, -2, -3, -4, -10, -1, -6] => [-8, -9, -7, -5, -2, -3, -4, -10, -1, -6]
a = list(range(-5,0))
random.shuffle(a)
print('Original: {}'.format(a))
def sort_odd(x):
#
print(sort_odd(a))
===== Úlohy na doma =====
==== Úloha 4 - Najdi řetězec v dalším řetězci ====
V Pythonu existuje metoda ''%%str.find()%%'', která hledá ve vstupním řetězci ''%%a%%'' řetězec ''%%b%%'' (''%%a.find(b)%%''). Napište funkci ''%%find_str%%'', která bude fungovat obdobně jako metoda ''%%str.find()%%''. Tedy:
* Pokud řetězec ''%%a%%'' obsahuje řetězec ''%%b%%'', funkce vrátí první výsky (index prvního výskytu) řetězce ''%%b%%''
* Pokud řetězec ''%%a%%'' neobsahuje řetězec ''%%b%%'', funkce vrátí hodnotu -1
# Příklad metody str.find()
a = 'mechanotherapy'
b = 'another'
print(a.find(b))
print(a.find('that'))
def find_str(a,b):
#
==== Úloha 5 - Nahraď výskyt ====
V Pythonu existuje metoda ''%%str.replace()%%'', která ve vstupním řetězci ''%%a%%'' nahradí všechny výskyty řetězce ''%%b%%'' řetězcem ''%%c%%'' (''%%a.replace(b,c)%%''). Napište funkci ''%%replace_str%%'', která bude fungovat obdobně jako metoda ''%%str.replace()%%''. Tedy:
* Pokud řetězec ''%%a%%'' obsahuje řetězec ''%%b%%'', funkce nahradí všechny výskyty řetězce ''%%b%%'' řetězcem ''%%c%%''
* Pokud řetězec ''%%a%%'' neobsahuje řetězec ''%%b%%'', funkce vrátí řetězec ''%%a%%''
* (Nepovinné) Využijte Vámi napsanou funkci ''%%find_str%%''
# Příklad metody str.replace(a, b):
a = 'mechanotherapy'
b = 'mechano'
c = 'hydro'
print(a.replace(b, c))
def replace_str(a,b,c):
#
==== Úloha 6 - Druhý největší prvek v poli ====
Najdi druhý největší prvek v poli a také jeho index. Pokuste se pro nalezení využít řazení.