C2142 Návrh algoritmů pro přírodovědce
4. Řazení
Tomáš Raček
Jaro 2017
Sekvenční vyhledávání
Problém. Uvažme problém nalezení prvku v poli. Tento lze zřejmě
řešit s lineární složitostí.
def search(array, k):
for i in range(len(array)):
if array[i] == k:
return i
return None
Zamyšlení. Pokud by bylo pole seřazeno, vyhledávání v něm by
mohlo být snazší.
• Jak náročné je vyhledávání v seřazeném poli?
• Jak náročné je seřadit pole?
Binární vyhledávání I
Myšlenka. Pole je seřazeno ⇔ pro každý prvek pole platí, že
hodnoty vlevo od něj jsou menší nebo rovny tomuto prvku a vpravo
od něj větší nebo rovny.
Příklad. Vyhledávání čísla 76.
Binární vyhledávání II
Rekurzivní implementace binárního vyhledávání:
def binary_search(A, k, i_min, i_max):
if i_max < i_min:
return None
mid = (i_min + i_max) // 2
if k == A[mid]:
return mid
elif k < A[mid]:
return binary_search(A, k, i_min, mid - 1)
else:
return binary_search(A, k, mid + 1, i_max)
Složitost. V každé iteraci se velikost prohledávané oblasti zmenší na
polovinu. Složitost binárního vyhledávání je tedy O(log n).
Problém řazení
Neformální definice:
Vstup: Posloupnost prvků a1, . . . , an délky n
Výstup: Neklesající permutace vstupní posloupnosti, tj.
∀i ∈ {1, . . . , n − 1} : ai ≤ ai+1
Poznámka k definici. Formální definice pracuje s prvky tvaru (ai, Di),
kde ai jsou klíče (podle kterých se řadí) a Di pak další data, která
mají význam v praktických aplikacích. Při analýze algoritmů je
většinou zanedbáme (Di = ∅).
Poznámka k terminologii. Někdy se nesprávně používá pro řazení
výraz třídění, které značí ale spíše seskupování objektů podle
daných vlastností.
Selection sort
Myšlenka. Najdi v poli nejmenší prvek a vyměň jej s prvkem na první
pozici. Opakuj postup pro zbytek pole (bez prvního prvku).
def selection_sort(A):
for i in range(len(A)):
min_idx = i
for j in range(i, len(A)):
if A[min_idx] > A[j]:
min_idx = j
A[min_idx], A[i] = A[i], A[min_idx]
Složitost. Vnější for cyklus zjevně O(n), vnitřní má však různé délky
(n, n - 1,…, 1). Celkem tedy 1 + 2 + …+ n ∈ O(n2).
Bubble sort
Myšlenka. Porovnávám postupně prvky na sousedních pozicích.
Pokud jsou vůči sobě dva v nesprávném pořadí, prohodím je.
Důsledek. Po první iteraci „probublá“ největší prvek na konec pole.
def bubble_sort(A):
for i in range(len(A)):
for j in range(len(A) - i - 1):
if A[j] > A[j + 1]:
A[j], A[j + 1] = A[j + 1], A[j]
Složitost. O(n2) podle stejné úvahy jako pro selection sort. Složitost
lze vylepšit na příznivých datech. Jak?
Insertion sort
Myšlenka. Rozdělme (virtuálně) pole na dvě části: (1) už seřazenou a
(2) dosud neseřazenou. Vždy první prvek z (2) zařazujeme korektně
do (1).
def insertion_sort(A):
for i in range(len(A)):
item = A[i]
j = i
while j > 0 and item < A[j - 1]:
A[j] = A[j - 1]
j -= 1
A[j] = item
Složitost. Pro nejhorší případ (pole seřazeno v opačném pořadí) je
složitost O(n2).
Složitost problému řazení
Idea důkazu. Uvažme posloupnosti složené pouze z čísel 1,…,n, kde
se každé číslo vyskytuje nejvýše jednou (= permutace této množiny).
Takových je zjevně n!.
Asociativní řadicí algoritmy mohou provádět pouze porovnání
dvojice prvků.
Korektní řadicí algoritmus musí pro každou takovouto posloupnost
provést jiný výpočet.
Libovolný asociativní řadicí algoritmus musí tyto výpočty odlišit, tj.
provést alespoň log2(n!) binárních testů.
Důsledek. Dolní odhad složitosti řazení je Ω(n log n).
Quick sort
Myšlenka. Vyberu prvek pole. Vlevo od něj přesunu všechny menší
prvky, vpravo od něj větší. Obě tyto části pak řadím dále rekurzivně
stejným postupem.
def quick_sort(array):
if len(array) <= 1:
return array
else:
pivot = array[0]
smaller = [x for x in array[1:] if x < pivot]
bigger = [x for x in array[1:] if x >= pivot]
return quick_sort(smaller) + [pivot] + quick_sort(bigger)
Složitost. V nejhorším případě (libovolně seřazené pole) bude
hloubka rekurzivního volání O(n), v každé úrovni je potřeba rozdělit
prvky do dvou částí se složitostí O(n). Celkem tedy O(n2).
Merge sort
Idea. Uvažme dvě již seřazené posloupnosti. Jak z nich vytvořit
jednu seřazenou?
Funkce merge(A, B)
• porovnává vždy první prvky obou posloupností, menší z nich
přesune do výstupní posloupnosti
Merge sort
• seřazenou posloupnost délky n získám ze dvou seřazených
posloupností délky n/2 aplikací funkce merge
• analogicky posloupnosti velikosti n/2 „slévám“ ze dvou
seřazených posloupností o velikosti n/4
• posloupnosti délky 1 jsou implicitně seřazeny
Merge sort – ukázka
Merge sort – implementace
def merge(A, B):
if len(A) == 0:
return B
if len(B) == 0:
return A
if A[0] < B[0]:
return [A[0]] + merge(A[1:], B)
else:
return [B[0]] + merge(A, B[1:])
def merge_sort(A):
if len(A) <= 1:
return A
mid = len(A) // 2
return merge(merge_sort(A[:mid]), merge_sort(A[mid:]))
Merge sort – složitost
Složitost merge sortu
• funkce merge má složitost O(n)
• počet úrovní volání funkce funkce merge je O(log n)
• složitost merge sortu je O(n log n)
Pozorování
• dolní odhad složitosti problému řazení je Ω(n log n)
• složitost merge sortu je O(n log n)
Závěr. Merge sort je optimální algoritmus pro problém řazení se
složitostí O(n log n).
Stabilita řadicích algoritmů
Definice. Řadicí algoritmus je stabilní, pokud neprohazuje prvky se
stejným klíčem.
Příklad. Uvažme seznam lidí seřazených podle jména. Pokud jej
sežadíme dále stabilním algoritmem podle příjmení, získáme
seznam seřazený podle příjmení a jména.
Přirozenost řadicích algoritmů
Definice. Řadicí algoritmus je přirozený, pokud dokáže využít
předuspořádání vstupní posloupnosti.
Důsledek. Přirozené řadicí algoritmy řadí částečně seřazené
posloupnosti v lepším čase.
Příklad. Modifikace algoritmu bubble sort:
def bubble_sort(A):
for i in range(len(A)):
swapped = False
for j in range(len(A) - i - 1):
if A[j] > A[j + 1]:
A[j], A[j + 1] = A[j + 1], A[j]
swapped = True
if not swapped:
return
Součet čísel
Experiment. Určete součet zadaného souboru reálných čísel.
Řešení. V Pythonu například funkce sum nebo explicitně:
total = 0
for item in array:
total += item
Pozorování. Uvažme stejnou sadu čísel, jen v jiném (zcela náhodně
zvoleném) pořadí.
array2 = sorted(array, key = lambda k : random.random())
Zřejmě platí:
sum(array) == sum(array2)
Nebo ne?
Asociativita sčítání reálných čísel
Příklad. Uvažme výpočet 1,11 + 0,001 s přesností na 3 platné číslice.
Poznámka. Počet platných desítkových číslic pro typ float je
průměrně 7, pro typ double pak 16.
• 1,11 + 0,001 = 1,11
• korektní výsledek v rámci zvolené přesnosti
Srovnejme
• 1,11 + 0,001 + …+ 0,001
• 1,11 + (0,001 + …+ 0,001)
Závěr. Sčítání reálných čísel není asociativní.
Doporučení. Pokud je přesnost důležitá, sčítám čísla v pořadí podle
jejich (absolutní) velikosti.