Úvod Třídění Vyhledávání Shrnutí Třídění a vyhledávání Úvod Třídění Vyhledávání Shrnutí Obsah 1 Úvod 2 Třídění Bubble sort Select sort Insert sort Quick sort Merge sort Radix sort 3 Vyhledávání Vyhledávání v poli Vyhledávací stromy 4 Shrnutí Úvod Třídění Vyhledávání Shrnutí Komentář k přednášce mnoho různých algoritmů pro stejný účel ­ třídění většina programovacích jazyků má vestavěnou podporu (funkce sort()) Proč se tím tedy zabýváme? Úvod Třídění Vyhledávání Shrnutí Komentář k přednášce Proč se tím tedy zabýváme? 1 tradice 2 ilustrace algoritmického myšlení, technik návrhu algoritmů 3 ilustrace drobné změny algoritmu s velkým dopadem na rychlost programu 4 hezky se to vizualizuje a vysvětluje Úvod Třídění Vyhledávání Shrnutí Doporučený zdroj http://www.sorting-algorithms.com/ animace kódy vizualizace Více podobných: Google sorting algorithms Úvod Třídění Vyhledávání Shrnutí Třídění: problém vstup: posloupnost (přirozených) čísel např. 8, 2, 14, 3, 7, 9 výstup: setříděná posloupnost např. 2, 3, 7, 8, 9, 14 Úvod Třídění Vyhledávání Shrnutí Co vy na to? zkuste vymyslet třídící algoritmus co nejvíce různých principů co nejefektivnější algoritmus možná inspirace: jak třídíte karty? Úvod Třídění Vyhledávání Shrnutí Složitost n ­ délka vstupní posloupnosti počet operací jednoduché algoritmy O(n2 ), ,,kvadratická složitější algoritmy O(n log(n)) Úvod Třídění Vyhledávání Shrnutí Bubble sort Bubble sort probublávání vyšších hodnot nahoru srovnávání a prohazování sousedů for i = 1:n for j = n:i+1 if a[j] < a[j-1], swap a[j,j-1] //invariant: a[1..i] in final position Úvod Třídění Vyhledávání Shrnutí Select sort Select sort třídění výběrem projdeme dosud nesetříděnou část pole a výbereme nejmenší prvek nejmenší prvek zařadíme na aktuální pozici (výměnou) Úvod Třídění Vyhledávání Shrnutí Select sort Select sort Úvod Třídění Vyhledávání Shrnutí Insert sort Insert sort zatřiďování prefix pole udržujeme setříděný každou další hodnotu zařadíme tam, kam patří ,,třídění karet Úvod Třídění Vyhledávání Shrnutí Insert sort Insert sort Úvod Třídění Vyhledávání Shrnutí Quick sort Quick sort rekurzivní algoritmus vybereme ,,pivota a pole rozdělíme na dvě části: větší než pivot menší než pivot obě části pak nezávisle setřídíme (rekurzivně pomocí quick sortu) Úvod Třídění Vyhledávání Shrnutí Quick sort Quick sort ilustrace Úvod Třídění Vyhledávání Shrnutí Quick sort Quick sort pokud máme smůlu při výběru pivota, tak je stejně pomalý jako předchozí v průměrném případě je rychlý (O(n log(n))) ­quick Úvod Třídění Vyhledávání Shrnutí Merge sort Merge sort rekurzivní algoritmus pole rozdělíme na dvě poloviny a ty setřídíme (merge sort) ze setříděných polovin vyrobíme jedno setříděné pole ­ ,,zipování Úvod Třídění Vyhledávání Shrnutí Merge sort Merge sort Úvod Třídění Vyhledávání Shrnutí Merge sort Operace Merge Úvod Třídění Vyhledávání Shrnutí Radix sort Radix sort předchozí algoritmy využívají pouze operaci porovnání dvou hodnot aplikovatelné na cokoliv, co lze porovnávat, žádné další předpoklady s doplňujícími předpoklady můžeme dostat nové algoritmy (obecný princip) Úvod Třídění Vyhledávání Shrnutí Radix sort Radix sort aplikovatelné na (krátká) čísla postupujeme od nejméně významné cifry k nejvýznamější setřídíme pole podle dané cifry = rozdělení do 10 ,,kyblíčků (jednoduché, rychlé) Úvod Třídění Vyhledávání Shrnutí Radix sort Radix sort ilustrace Úvod Třídění Vyhledávání Shrnutí Vyhledávání: hra myslím si přirozené číslo X mezi 1 a 1000 povolená otázka: ,,Je X menší než N? kolik otázek potřebujete na odhalení čísla? (kolik předem formulovaných otázek potřebujete?) Úvod Třídění Vyhledávání Shrnutí Vyhledávání: problém mnoho různých variant, základní verze: vstup: setříděná posloupnost čísel + dotaz (číslo) např. 2, 3, 7, 8, 9, 14 + dotaz 8 výstup: index hledaného čísla v posloupnosti (případně 0 pokud tam není) např. 4 Úvod Třídění Vyhledávání Shrnutí Vyhledávání a logaritmus zjednodušeně platí: základní metoda: půlení intervalu rozumné vyhledávání ­ logaritmický počet kroků (vzhledem k délce seznamu) lineární vyhledávání ­ jen velmi krátké seznamy Úvod Třídění Vyhledávání Shrnutí Vyhledávání v poli Vyhledávání půlením intervalu Úvod Třídění Vyhledávání Shrnutí Vyhledávání v poli Vyhledávání půlením intervalu (rekurzivně) Úvod Třídění Vyhledávání Shrnutí Vyhledávací stromy Vyhledávací stromy Úvod Třídění Vyhledávání Shrnutí Shrnutí třídící algoritmy: jednoduché (kvadratické): bubble, selection, insertion složitější (n log n, rekurzivní): quick sort, merge sort vyhledávání: půlení intervalu, rekurze