Vyhledávání, řazení, složitost IB111 Programování a algoritmizace 2011 Otrávené studny 8 studen, jedna z nich je otrávená laboratorní rozbor dokáže rozpoznat přítomnost jedu ve vodě je drahý (je časově náročný) kolik rozborů (času) potřebujeme? jak určit otrávenou studnu? Otrávené studny: řešení studna kód studna kód A 000 E 100 B 001 F 101 C 010 G 110 D 011 H 111 test přidělené studny 1 B, D, F, H 2 C, D, G, H 3 E, F, G, H 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? Mezi kolika čísly jste schopni odhalit skryté číslo na K otázek? Vyhledávání: řešení „dynamické otázky : půlení intervalu „předem formulované otázky : dotazy na bity v bitovém zápisu (stejně jako u studen) N čísel: potřebujeme log2 N otázek K otázek: rozlišíme mezi 2K čísly Vyhledávání: problém mnoho různých variant, základní verze: vstup: seřazená posloupnost čísel + dotaz (číslo) např. 2, 3, 7, 8, 9, 14 + dotaz 8 výstup: index hledaného čísla v posloupnosti (případně -1 pokud tam není) např. 3 Vyhledávání a logaritmus naivní metoda = průchod seznamu lineární vyhledávání, O(n) pomalé (viz např. databáze s milióny záznamů) jen velmi krátké seznamy základní rozumná metoda = půlení intervalu analogicky hře s hádáním čísel podívám se na prostřední člen podle jeho hodnoty pokračuji v levém/pravém intervalu logaritmický počet kroků (vzhledem k délce seznamu), O(log(n)) Vyhledávání půlením intervalu (rekurzivně) Vyhledávání půlením intervalu (iterativně) Upozornění k uvedeným algoritmům předchozí (a následující) pseudokódy nejsou přímo v Pythonu hlavní rozdíl: indexování od 0 vs od 1 záměr: abyste trénovali čtení různých notací budeme dělat na cvičení, tak abyste nemohli jen tak přepsat kód ze slidů Vyhledávací stromy (více později) Řadicí algoritmy: terminologická poznámka anglicky „sorting algorithm česky používáno: řadicí algoritmy nebo třídicí algoritmy řadicí obecně (ale nikoliv jednoznačně) považováno za „správnější Řadicí algoritmy: komentář mnoho různých algoritmů pro stejný účel většina programovacích jazyků má vestavěnou podporu (funkce sort()) Proč se tím tedy zabýváme? Řadicí algoritmy: komentář Proč se tím tedy zabýváme? 1 ilustrace algoritmického myšlení, technik návrhu algoritmů 2 ilustrace drobné změny algoritmu s velkým dopadem na rychlost programu 3 tradice, hezky se to vizualizuje a vysvětluje Doporučený zdroj http://www.sorting-algorithms.com/ animace kódy vizualizace Více podobných: Google → sorting algorithms Řadicí algoritmy: problém vstup: posloupnost (přirozených) čísel např. 8, 2, 14, 3, 7, 9 výstup: seřazená posloupnost např. 2, 3, 7, 8, 9, 14 Co vy na to? zkuste vymyslet řadicí algoritmus co nejvíce různých principů co nejefektivnější algoritmus možná inspirace: jak řadíte karty? Složitost n – délka vstupní posloupnosti počet operací jednoduché algoritmy O(n2 ), „kvadratická složitější algoritmy O(n log(n)) Bublinkové řazení (Bubble sort) „probublávání vyšších hodnot nahoru srovnávání a prohazování sousedů for i in range(n): print a for j in range(n-i-1): if a[j] > a[j+1]: tmp = a[j] a[j] = a[j+1] a[j+1] = tmp invariant cyklu: a[n-i-1..n-1] ve finální pozici Bublinkové řazení: příklad běhu [8, 2, 7, 14, 3, 1] [2, 7, 8, 3, 1, 14] [2, 7, 3, 1, 8, 14] [2, 3, 1, 7, 8, 14] [2, 1, 3, 7, 8, 14] [1, 2, 3, 7, 8, 14] Řazení výběrem (Select sort) řazení výběrem projdeme dosud neseřazenou část pole a vybereme nejmenší prvek nejmenší prvek zařadíme na aktuální pozici (výměnou) Řazení výběrem (Select sort) Řazení vkládáním (Insert sort) podobně jako „řazení karet prefix pole udržujeme seřazený každou další hodnotu zařadíme tam, kam patří Řazení vkládáním (Insert sort) Quicksort rekurzivní algoritmus vybereme „pivota a pole rozdělíme na dvě části: větší než pivot menší než pivot obě části pak nezávisle seřadíme (rekurzivně pomocí quicksortu) Quick sort ilustrace 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ý – quick O(n log(n)) Řazení slučováním (Merge sort) rekurzivní algoritmus pole rozdělíme na dvě poloviny a ty seřadíme (pomocí Merge sort) ze seřazených polovin vyrobíme jedno seřazené pole – „zipování Merge sort Operace Merge 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) Radix sort aplikovatelné na (krátká) čísla postupujeme od nejméně významné cifry k nejvýznamnější seřadíme pole podle dané cifry = rozdělení do 10 „kyblíčků (jednoduché, rychlé) Radix sort ilustrace Složitost trochu podrobněji složitost algoritmu – jak je algoritmus výpočetně náročný časová, prostorová měříme počet operací nikoliv čas na konkrétním stroji vyjadřujeme jako funkci délky vstupu O notace – zanedbáváme konstanty např. O(n), O(n log(n)), O(n2 ) Ilustrace rozdílů v složitosti Složitost řadicích algoritmů n – délka vstupní posloupnosti počet operací jednoduché algoritmy O(n2 ), „kvadratická složitější algoritmy O(n log(n)) Shrnutí vyhledávání: půlení intervalu, rekurze řadicí algoritmy: jednoduché (kvadratické): bubble, selection, insertion složitější (n log n, rekurzivní): quick sort, merge sort