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ů. Základní jsou dvě metody:

1. pomocí funkce sorted
2. pomocí medoty list.sort()

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

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]))

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))

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))

Čí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)

a = get_unsorted(10)
b = copy.deepcopy(a)
 
 
def bubble_sort(a):
 
    # <vase_implementace>
 
bubble_sort(a)
print(a)
print(sorted(b))

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)

• 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)$

a = get_unsorted(10)
b = copy.deepcopy(a)
 
def selection_sort(a):
 
    # <vase_implementace>
 
selection_sort(a)
print(a)
print(sorted(b))

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))

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 <podmínka> vrátí chybu v případě, že je <podmínka> == False
            # podobně jako:
            # if not <podmínka>: raise AssertionError()
 
    print(f.__name__,"sort test passed")

Magic funkce jsou součástí IPythonu (seznam dostupných Magic funkcí).

%whos

%time test_sort(f=bubble_sort, repeats=50, length=1000)

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):
 
    # <vase_implementace>
 
print(sort_odd(a))

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):
 
    # <vas_kod>

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):
 
    # <vas_kod>

Najdi druhý největší prvek v poli a také jeho index. Pokuste se pro nalezení využít řazení.