## cvičení 8
## algoritmy nad seznamy
from random import randint
from timeit import Timer
from functools import partial

# ÚLOHA 1
# Napište program, který bude interagovat s uživatelem.
# Program spočítá počet písmen zadaného slova.
def count_letters():
    pass

# >>> count_letters()
# Zadej slovo, kterému mám spočítat písmena: >? Eldorado
# Slovo Eldorado má 8 písmen.


# ÚLOHA 2
# Napište funkci guess_number_human(upper_bound), která umožňuje hrát s počítačem
# hru na hádání čísla: počítač si myslí číslo (celé číslo v intervalu [1, upper_bound]),
# hráč se ho snaží uhodnout. Po každém pokusu dostane hráč od počítače informaci, zda je
# hledané číslo menší nebo větší než to, které si tipnul.
def guess_number_human(upper_bound):
    pass

# >>> guess_number_human(10)
# --- pokus c. 1 ---
# Zadej svuj tip: 5
# Moje cislo je mensi.
# --- pokus c. 2 ---
# Zadej svuj tip: 3
# Moje cislo je vetsi.
# --- pokus c. 3 ---
# Zadej svuj tip: 4
# Jo, to je ono!


# ÚLOHA 3
# Napište funkci, která vyhledá v setříděném seznamu <array> prvek <item>.
# Funkce buď vrátí index prvku, nebo None, pokud se prvek v seznamu nenachází.
# Seznam procházejte lineárně, nepoužívejte konstrukce <a in array> ani <array.index(a)>.
# Funkce bude čistá, nebude modifikovat zadaný seznam.
def my_search(numbers):
    pass

# vzorový výstup:
# >>> array = [randint(1, 1000) for _ in range(1000)]
# >>> array.sort()
# >>> my_search(array, 42)
# 24
# >>> array = [randint(1, 1000) for _ in range(1000)]
# >>> array.sort()
# >>> my_search(array, 42)
# None


# ÚLOHA 4
# Napište funkci, která v binárně vyhledá v setříděném seznamu <array> prvek <item>.
# Funkce buď vrátí index prvku, nebo None, pokud se prvek v seznamu nenachází.
# Individálně nastudujte, jak funguje binární vyhledávání.
def binary_search(numbers):
    pass

# vzorový výstup:
# >>> array = [randint(1, 1000) for _ in range(1000)]
# >>> array.sort()
# >>> binary_search(array, 42)
# 12
# >>> array = [randint(1, 1000) for _ in range(1000)]
# >>> array.sort()
# >>> binary_search(array, 42)
# None


# ÚLOHA 5
# Nastudujte třídící algoritmus dle vaší místnosti:
# 1. Insertion sort
# 2. Selection sort
# 3. Bubble sort
# 4. Quick sort
#
# Naprogramujte váš řadící algoritmus:
# Algoritmus nesmí využívat funkce <sorted(array)> nebo <array.sort()>
def my_sort(numbers):
    pass

# vzorový výstup:
# >>> array = [randint(1, 100) for i in range(100)]
# >>> my_sort(array)
# [1, 2, 4, 5, 5, 7, 12, ..., 97, 99, 99]


# TEST RYCHLOSTI
# Spusťe funkci compare_sort() a porovnejte, jestli je vaše implementace rychlejší
# než zabudovaná funkce pyhonu <sorted()>.
def compare_sort(lenght):
    array = [randint(1, 10000) for _ in range(lenght)]
    python_sort_test = Timer(partial(sorted, array))
    array = [randint(1, 10000) for _ in range(lenght)]
    my_sort_test = Timer(partial(my_sort, array))
    print("sorted():\t", python_sort_test.timeit(100))
    print("my_sort():\t", my_sort_test.timeit(100))


if __name__ == "__main__":
    # zde můžete volat implementované funkce a zkusit si, jak fungují
    compare_sort(1000)
    pass
