7. Algoritmy nad seznamy¶

Přístup do seznamů

Operace se seznamy

Kopírování seznamu

Vnořené seznamy

7.1. Pascalův trojúhelník¶

7.1.1. Trojúhelník¶

Napište funkci triangle(n), která vrací seznam n seznamů takových, že první obsahuje 1 jedničku, druhý 2 jedničky až poslední n jedniček.

def triangle(n: int) -> List[List[int]]:
    pass

def test_triangle() -> None:
    assert triangle(0) == []
    assert triangle(1) == [[1]]
    assert triangle(3) == [[1], [1, 1], [1, 1, 1]]
    assert triangle(5) == [[1], [1, 1], [1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1, 1]]

7.1.2. Pascalův trojúhelník – kombinační čísla¶

Napište funkci pascal_binomial(n), která vrací n řádků Pascalova trojúhelníku. Trojúhelník bude reprezentovaný jako seznam řádků, kde každý řádek je seznam hodnot v trojúhelníku. Funkce by měla hodnoty napočítávat pomocí kombinačních čísel a měla by využívat následující strukturu.

def factorial(n: int) -> int:
    pass

def binomial_coefficient(n: int, k: int) -> int:
    pass

def pascal_binomial(n: int) -> List[List[int]]:
    pass

def test_pascal_binomial() -> None:
    assert pascal_binomial(0) == []
    assert pascal_binomial(1) == [[1]]
    assert pascal_binomial(3) == [[1], [1, 1], [1, 2, 1]]
    assert pascal_binomial(5) == [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

7.1.3. Pascalův trojúhelník – z předchozího řádku¶

Napište funkci pascal(n), která vrací n řádků Pascalova trojúhelníku. Trojúhelník bude reprezentovaný jako seznam řádků, kde každý řádek je seznam hodnot v trojúhelníku. Funkce by měla hodnoty napočítávat jako součet hodnot z předchozího řádku.

Pro vykreslení trojúhelníku můžete použít pomocnou funkci print_pascal (tato funkce nebude fungovat v online prostředí).

def pascal(n: int) -> List[List[int]]:
    pass

def test_pascal() -> None:
    assert pascal(0) == []
    assert pascal(1) == [[1]]
    assert pascal(3) == [[1], [1, 1], [1, 2, 1]]
    assert pascal(5) == [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

def print_pascal(pascal: List[List[int]]) -> None:
    max_number_size = len(str(pascal[-1][len(pascal)//2])) + 2
    for row in pascal:
        line = ""
        for x in row:
            line += ("{0: ^" + str(max_number_size) + "}").format(x)
        print(("{0: ^" + str(max_number_size * len(pascal[-1])) + "}").format(line))
# print_pascal(pascal(7))

7.2. Řadicí algoritmy¶

Řadicí algoritmy mají za úkol seřadit daný seznam (typicky čísel) od nejmenšího po největší (samozřejmě lze řadit i naopak). Takových algoritmů je celá řada a mají různé strategie a vlastnosti. Ve většině programovacích jazyků včetně Pythonu je nějaký řadicí algoritmus již implementován. Vlastní implementace řazení je zde jen z tréningových důvodů. Volba špatného řadícího algoritmu, špatná implementace či ignorování vestavěných může vést k neočekávanému chování programů, jak ilustruje kóan Letní šála. Pro lepší představu jak algoritmy pracují existuje na internetu mnoho vizualizací, které se snaží princip každého algoritmu názorně ukázat (např. http://www.sorting-algorithms.com nebo http://sortvis.org/).

Vaše implementace řadících algoritmů by měla pracovat se zadaným seznamem a ten upravovat, tj. funkce nic nevrací jen prohazuje položky v daném seznamu. (prohodit obsah dvou proměnných v Pythonu lze snadno pomocí a, b = b, a)

Testovací funkce:

::

def sort_tester(sorting_function: Callable[[List[int]], None]) -> None:

lists = [: [7, 6, 100, 3, 2, 11, -1, 10, 10, 42, 42, 42, 2, 13, 0, -5]

]

for lst in lists:

returned = sorting_function(lst) if returned:

lst = returned

for i in range(1, len(lst)):: assert lst[i - 1] <= lst[i]

7.2.1. Bubble sort¶

Implementujte Bubble sort.

def bubble_sort(l: List[int]) -> None:
    pass

def test_bubble_sort() -> None:
    sort_tester(bubble_sort)

7.2.2. Select sort¶

Implementujte Select sort.

def select_sort(l: List[int]) -> None:
    pass

def test_select_sort() -> None:
    sort_tester(select_sort)

7.2.3. Insert sort¶

Implementujte Insert sort.

def insert_sort(l: List[int]) -> None:
    pass

def test_insert_sort() -> None:
    sort_tester(insert_sort)

7.2.4. Analýza rychlosti¶

Proveďte experimentálně analýzu všech naimplementovaných řadících algoritmů. Buď můžete vaše funkce doplnit o počítání provedených elementárních operací (porovnávání a přiřazení) nebo můžete měřit čas nutný k seřazení velkých polí pomocí time.time(). Napište si pomocné funkce pro generování polí zadané délky (a s různými vlastnostmi: úplně náhodné, téměř seřazené, obrácená posloupnost) a zkoušejte, u kterých algoritmů se tyto vlastnosti seznamu projeví. Porovnejte svoje algoritmy i s vestavěnou metodou list.sort().

7.2.5. Quick sort¶

Implementujte Quick sort. Funkce nemusí měnit původní seznam (může vrátit nový, seřazený).

def quick_sort(l: List[int]) -> List[int]:
    pass

def test_quick_sort() -> None:
    sort_tester(quick_sort)

7.2.6. Merge sort¶

Implementujte Merge sort. Funkce nemusí měnit původní seznam (může vrátit nový, seřazený).

def merge_sort(l: List[int]) -> List[int]:
    pass

def test_merge_sort() -> None:
    sort_tester(merge_sort)

7.2.7. Counting sort¶

Implementujte Counting sort. Funkce nemusí měnit původní seznam (může vrátit nový, seřazený). Upozornění: algoritmus je vhodný pokud počet možných hodnot prvků je výrazně menší než jejich počet.

def counting_sort(l: List[int], lower: int, upper: int) -> List[int]:
    pass

def test_counting_sort() -> None:
    lst = [7, 2, 6, 10, 3, -2, -10, 10, 10, 2, 4, 0, -5]

    lst = counting_sort(lst, -10, 10)
    for i in range(1, len(lst)):
        assert lst[i - 1] <= lst[i]

7.2.8. Radix sort¶

Implementujte Radix sort. Funkce nemusí měnit původní seznam (může vrátit nový, seřazený).

def radix_sort(l: List[int]) -> List[int]:
    pass

def test_radix_sort() -> None:
    sort_tester(radix_sort)

7.3. Neefektivní řadící algoritmy¶

Next Section - 8. Datové struktury