import time
from random import randint
# edulint: config=cs0

# Implementujte bubble sort. Funkce by mela upravit predany seznam.
def bubble_sort(alist):
    pass

def test_bubble_sort():
    alist = [1, 5, 4, 18, 3, 24, -1, 5, 0]
    bubble_sort(alist)
    assert alist == [-1, 0, 1, 3, 4, 5, 5, 18, 24]

# test_bubble_sort()

# Bubble sort ukol c. 2: sepiste upravenou fci tak, aby po kazde zmene vypsala seznam.
def bubble_sort_with_list_print(alist):
    pass

# bubble_sort_with_list_print([1, 5, 4, 18, 3, 24, -1, 5, 0])

# Bubble sort ukol c. 3: sepiste upravenou fci tak, aby na konci vypsala pocet prohozeni
# hodnot v ramci cele fce. (Jako prohozeni pocitame vzajemny presun dvojice prvku.)
def bubble_sort_with_swap_count_print(alist):
    pass

# bubble_sort_with_swap_count_print([1, 5, 4, 18, 3, 24, -1, 5, 0]) # prohozeni optimalne 18

# Implementujte insert sort. Funkce by mela upravit predany seznam.
def insert_sort(alist):
    pass

def test_insert_sort():
    alist = [1, 5, 4, 18, 3, 24, -1, 5, 0]
    insert_sort(alist)
    assert alist == [-1, 0, 1, 3, 4, 5, 5, 18, 24]

# test_insert_sort()

# Insert sort ukol c.2: sepiste upravenou fci tak, aby po kazde zmene vypsala seznam
# a na konci vypsala pocet prohozeni hodnot v ramci cele fce. (Jako prohozeni pocitame
# kazdou zmenu provedenou v seznamu.)
def insert_sort_with_both_print(alist):
    pass

# insert_sort_with_both_print([1, 5, 4, 18, 3, 24, -1, 5, 0]) # prohozeni optimalne 27

# Otazka k zamysleni: ktery tridici algoritmus je efektivnejsi? Proc?

# Pro bubble sort i insert sort napiste test, ktery otestuje, zda fce vrati spravny vysledek
# v okrajovych pripadech (a otestujte sve fce, idealne varianty s vypisem):
#  - prazdny seznam
#  - jednoprvkovy seznam
#  - uz serazeny seznam
#  - seznam identickych prvku
# (testy muzou byt stejne, staci zmenit, kterou fci volate)
def my_test_bubble_sort():
    pass

# my_test_bubble_sort()

def my_test_insert_sort():
    pass

# my_test_insert_sort()

# Pomocna funkce k dalsimu ukolu.
# Volani measure_sort_time(bubble_sort, [5, 2, 1, 3]) vrati cas v s, ktery trvalo fci bubble_sort
# seradit seznam [5, 2, 1, 3]. (Pro ostatni fce je zapis obdobny.)
def measure_sort_time(sort_function, test_list):
    start_time = time.time()
    sort_function(test_list)
    return time.time() - start_time

# Napiste fci, ktera pro bubble sort, insert sort a vestavenou fci sorted vypise, jak dlouho
# jim trva seradit seznam nahodnych cisel od 0 do 10**6 o velikosti 7000 prvku.
# Pro mereni casu muzete pouzit funkci vyse.
# (Nechcete si vytvorit funkci na generovani nahodneho seznamu?)
def compare_sort_speed():
    pass

# compare_sort_speed()

# Ktery z algoritmu je nejrychlejsi? Ktery nejpomalejsi?

# Implementujte quick sort. Funkce by mela upravit predany seznam.
def quick_sort(alist):
    pass

def test_quick_sort():
    alist = [1, 5, 4, 18, 3, 24, -1, 5, 0]
    quick_sort(alist)
    assert alist == [-1, 0, 1, 3, 4, 5, 5, 18, 24]

# test_quick_sort()

# Quick sort nasledne otestujte na okrajovych pripadech z predchozich uloh a porovnejte
# jeho rychlost s ostatnimi algoritmy.