Třídící a vyhledávací algoritmy - Bečvář 2020

Třídící algoritmy (řadící)

Úvod:

• uspořádání sady datových záznamů
• vstupní data (soubor dvojic: klíč + hodnota
• rozlišujeme:

    o   vnitřní/vnější – jestli prvky známe, nebo je nejprve musíme načíst

    o   složitost

    o   přirozenost – rychleji pracují s již seřazenou hodnotou

    o   stabilita – zachová dvojice klíč + hodnot při výskytu několika stejných hodnot

    o   potřeba další operační paměti – pokud ne tak označováno jako O(1) – jinak třeba O(N)

 

Složitost:

• asymptotická složitost
• vztah na n prvků daného seznamu 

    o   min dolní mez: O(n) – potřeba každý prvek min jednou přečíst

• counting sort (počítá výskyt hodnot), radix sort (řadí řetězec dle jednotlivých znaků)

    o   pro řazení, založené na porovnávání dvojic klíčů – min: O(n*log(n))

• heapsort, quicksort, merge sort

    o   pro malý objem dat se hodí algoritmy s O(n²)

• bubble sort, insertion sort, selection sort, shell sort – nejrychlejší kvadratický

Neexistuje ideální řadící algoritmus hodící se vždy na všechno.

 

Tab viz: https://moodle.gybon.cz/mod/page/view.php?id=160

Vizualizace algoritmů: https://www.toptal.com/developers/sorting-algorithms

Vše: https://www.algoritmy.net/article/75/Porovnani-algoritmu

Bubble sort

https://www.algoritmy.net/article/3/Bubble-sort

• jednoduchý stabilní řadící algoritmus O(n²)

    o   vylepšením je shakesort (oboustranný bubble sort)

• porovnávám vždy dvojici (1. a 2., 2. a 3.) -> pokud je levá hodnota vyšší, než pravá prohodí si pořadí, tak až do konce nesetříděné části (když poprvé dojdeme na konec, poslední hodnota je nejmenší a v dalším ji už zkoušet nemusíme)

Shakesort

https://www.algoritmy.net/article/93/Shaker-sort

• stabilní řadící algoritmus O(n²)

    o   vylepšení bubble sortu

• porovnávám vždy dvojici (1. a 2., 2. a 3.) -> funguje jako bubble sort -> při průchodu DOPRAVA se „doprava posouvá“ vyšší hodnota z dvojice, při zpětném průchodu DOLEVA se „doleva posouvá“ menší hodnota z dvojice

Selection/Select sort

https://www.youtube.com/watch?v=g-PGLbMth_g

• Řazení výběrem
• Nepřirozený, nestabilní
• projdu všechny nesetříděné (udržuji si nejmenší hodnotu, na kterou jsem narazil O(1)) -> když dojdu nakonec, vyměním nejmenší hodnotu za první místo za setříděnými (nejvíc doleva)

Insertion sort

https://www.youtube.com/watch?v=OGzPmgsI-pQ

• Řazení vkládáním
• přirozený, stabilní
• O(n²) ale u téměř seřazeného pole se složitost blíží k O(n)
• pro n <= 10 je rychlejší než quicksort
• vylepšením může být (nestabilní) shell sort
• označíme první element jako setříděný -> (2) vždy pokračujeme od klíče o jedno dál, než jsou setříděné -> postupně ho porovnáváme dvojice (1 aktuální nesetřídění po jednom se setříděnými), když (vzestupně) najdeme takový, který je v setříděné skupině menší, než aktuálně testovaný -> testovaný je na svém místě -> posuneme hranici setříděných a opakujeme -> (2)

Shell sort 

https://www.youtube.com/watch?v=CmPA7zE8mx0 (goood)

https://www.youtube.com/watch?v=SHcPqUe2GZM

https://www.youtube.com/watch?v=1yDcmjLTWOg

• Nejvýkonnější kvadratický algoritmus
• Nepřirozený, nestabilní
• mezera třeba k=n/2 -> prvek na [1] koukne na prvek [1+k] -> srovnají se podle toho kdo má větší číslo, a když se prohodí, tak ten, co se prohazuje ještě kouká na prvek [pos - k] a zase se může prohodit -> až do konce a pak floor(k/2)

Heap sort 

https://www.algoritmy.net/article/17/Heapsort

https://www.youtube.com/watch?v=2DmK_H7IdTo

• = halda

    o   úplný binární strom – každý potomek vrcholku má nižší nebo stejnou hodnotu nežli vrcholek sám

• logaritmický O(n*log(n)) – zaručená složitost (vhodné pro realtime)
• rekurzivní – seřadit vždy jednotlivé haldy (trojúhelníky) tak, aby nahoře byl největší element, to provedeme pro všechny haldy, jakmile je největší element na vrcholku, vyměníme poslední z nesetříděných za nejvyšší element (v seznamu i v haldě a nejvyšší z haldy smažeme) – youtube pomůže dost!!! pokračujeme, dokud není setříděno

Merge sort

https://www.youtube.com/watch?v=4VqmGXwpLqc

• Řazení slučováním
• O(n*log(n))
• často rekurzivně
• „rozděl a panuj“
• rozdělíme na základní (jednotky) prvky -> z těch pak tvoříme seřazené dvojice -> pak dvě dvojice spojíme do čtveřice (kde přidáváme z dvojice vždy ten nižší prvek) -> dvě čtveřice na osmice

Quicksort

https://www.youtube.com/watch?v=Hoixgm4-P4M

https://www.youtube.com/watch?v=XE4VP_8Y0BU!!! dobré

• složitost O(n²) s očekávanou O(n*log(n))
• rychlé řazení
• rekurzivně
• pivot

    o   správná pozice v seznamu

    o   nalevo menší a napravo od pivotu větší hodnoty

• zvolíme pivot -> třeba první (poslední element) -> porovnání s elementem z druhého konce, pokud je na správném místě (menší vlevo, větší vpravo), zůstává a předá další element (bližší pivotu) k řazení. Takto se projdou všechny prvky až k pivotu -> pivot je na správném místě >>> opakujeme pro subřady

 

 

Vyhledávací algoritmy

Binární

• Platí pro sorted (setříděný) seznam; Podívá se doprostřed, zjistí, jestli je hodnota menší nebo větší, než hledá. Dále hledá ze správné poloviny, opět se podívá doprostřed atd…

Lineární

• Netříděný seznam; porovnává prvky postupně v řadě, jeden po druhém.

Backtracking

• Správná kombinace prvků (v poli) – např. šachovnice 8x8, mám umístit 8 královen, žádné dvě nejsou ve stejném 1. řádku, 2. sloupci ani 3. diagonále.
• „problém n královen“
• postupně hledáme správné řešení, pokud dosavadní řešení zjistíme, že není správné vracíme se o krok zpět a upravujeme předchozí řešení, pokud zjistíme, že takové není, vracíme se znovu zpět (existuje možnost neřešitelnosti)
• https://www.youtube.com/watch?v=0DeznFqrgAI