INOVACE BAKALÁŘSKÝCH A MAGISTERSKÝCH STUDIJNÍCH OBORŮ NA HORNICKO-GEOLOGICKÉ FAKULTĚ VYSOKÉ ŠKOLY BÁŇSKÉ - TECHNICKÉ UNIVERZITY OSTRAVA
Algoritmizace prostorových úloh Třídění, vyhledávání Daniela Szturcová
Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky. ESF napomáhá rozvoji lidských zdrojů a podnikatelského ducha.
Základní úlohy Velmi často využívanými algoritmy se ukazují algoritmy pro úlohy • třídění, • vyhledávání, • indexace.
Třídění Třídící (řadící) algoritmy slouží k setřízení prvků ze vstupního souboru podle určitého kriteria (například dle velikosti) vzestupně nebo sestupně. Důvod třídění – data uspořádat, efektivnější vyhledávání. Kritéria výběru vhodného algoritmu je dáno vlastnostmi algoritmu: • • • •
Složitost algoritmu (paměťová, časová), charakter vstupních dat, stabilita algoritmu, chování na částečně seřazených datech.
Třídění – vstupní data Vstupní data – jejich velikost – ovlivňují volbu metody. • Vnitřní algoritmy – data jsou uložena v operační paměti. InsertSort, BubbleSort, SelectSort – 2 O(N ) • Vnější algoritmy – rozsáhlá data se načítají z disku QuickSort, MergeSort – O(N log N)
Třídění – stabilita algoritmu •
•
•
•
•
Třídící algoritmy pracují se strukturovanými prvky, porovnávacím parametrem třídění je klíč. Stabilní algoritmy – uchovávají pořadí prvků podle klíče Nestabilní algoritmy – pořadí se během zpracování může měnit Snahou je volit strukturu dat tak, aby bylo možné použít stabilní algoritmy. Stabilita algortimu je užitečná při třídění podle dvou (či více) parametrů.
Třídění – seřazení dat Vstupní data obsahují část dat již uspořádaných podle kritéria. • Přirozené algoritmy – vykazují rychlejší průběh. • Nepřirozené – uspořádanost vstupních dat neprokazuje vliv na rychlost algoritmu.
Třídění – Bubble Sort Metoda bublinkového třídění. 2 Složitost O(N ). Prvky probublávají tak dlouho, až jsou ve výsledku data setříděna. Popis Bubble Sort: 1. 2.
3.
Porovnáváme sousední prvky. V případě splnění podmínky je vyměníme mezi sebou. Opakujeme, dokud průchod celou sadou je bez výměny sousedních prvků.
Třídění – Bubble Sort Ukázka bublinkového třídění na stránkách http://algoritmy.net.
Třídění – Insert Sort 2
Metoda přímého vkládání. Složitost O(N ). Data rozdělíme na "setříděnou" a “nesetříděnou” část. Prvky z nesetříděné části vložíme na odpovídající místo do setříděné části. Popis Insert Sort: 1. První prvek z nesetříděné části vložíme na pozici dle velikosti. 2. Prvky ze setříděné části ležící za vloženým prvkem posuneme o jednu pozici dozadu. 3. Opakujeme, dokud je v nesetříděné části alespoň jeden prvek.
Třídění – Insert Sort Ukázka přímého třídění na stránkách http://algoritmy.net.
Třídění – Select Sort 2
Metoda třídění výběrem. Složitost O(N ). Princip je postaven na výběru prvku a jeho uložení na odpovídající pozici (v případě sestupného třídění největší prvek na první pozici). Popis Select Sort: 1. Posloupnost prvků rozdělíme na setříděnou a nesetříděnou část. 2. V nesetříděné části vyhledáme největší prvek a uložíme jej na poslední pozici v setříděné části. 3. Proces opakujeme, doku nesetříděná část obsahuje alespoň jeden prvek.
Třídění – Insert Sort Ukázka třídění výběrem na stránkách http://algoritmy.net.
Třídění – Quick Sort Metoda rychlého třídění. 2 Složitost O(N log N), nejhorší případ O(N ). Využívá princip rozděl a panuj (Divide & Conquere), implementace často s rekurzí. Popis Quick Sort: 1. Volíme prvek – pivota. 2. Podle pivota rozdělíme posloupnost prvků do dvou částí, v jedné jsou menší a v druhé větší než pivot. 3. Opakujeme princip na každou vzniklou část, dokud bude obsahovat více než jeden prvek.
Třídění – Quick Sort Ukázka rychlého třídění na stránkách http://algoritmy.net.
Třídění – Merge Sort Metoda slévání. Složitost O(N log N). Principem je slévání dvou setříděných posloupností prvků do jedné výsledné. Využívá principu rozděl a panuj (Divide & Conquere), implementace využívá pomocné pole. Popis Merge Sort: 1. Vstupní posloupnost prvků rozdělíme na dvě stejně velké části. 2. Dělení (rekurze) skončí při jednotkové velikosti pole – triviálně setříděné. 3. Sléváme dvě vedlejší pole tak, že do výstupního vkládáme prvky podle výsledku porovnání. 4. Opakujeme, až je výstupem slévání celá posloupnost prvků.
Třídění – Merge Sort Ukázka třídění sléváním na stránkách http://algoritmy.net.
Třídění – výběr algoritmu Výběr vhodného algoritmu ovlivní řada kritérií. • Struktura vstupních dat. • Velikost operační paměti. • Znalost/náročnost implementace. Který algoritmus je nejlepší?
Vyhledávání
Základní úlohou je najít prvek při shodě klíče – vyhledávací kriterium. Množina klíčů S – vyhledávací prostor – vliv na výběr algoritmu.
Sekvenční vyhledávání Postupně procházíme všechny prvky prostoru S a porovnáváme je s klíčem, dokud nenajdeme hledaný prvek. • •
Na vstupu jsou neuspořádaná data. Složitost O(N).
Binární vyhledávání Lze najít i pod označením vyhledávání pomocí půlení intervalu. •
• •
Data na vstupu musí být uspořádána. Používá se rekurze. Složitost O(log N).
Literatura • •
http://www.algoritmy.net/ Korespondenční seminář z programování, https://ksp.mff.cuni.cz/