====== 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í.