07_razeni

• Maximální složitost: O(n^2) 
• Ve většině případů se ale blížíme k: O(n.log n) 
• nejrychlejší mezi běžnými algoritmy 
• pokud v datech hodně stejných hodnot, horší vlastnosti 
• princip 

• vyber pivot 

• ideálně rozděl data na 2 stejné části 
• např. první prvek 
• poslední prvek 
• medián (nejlepší), nutná apriorní znalost 

• rozděl hodnoty na menší a větší jak pivot 

• menší přemísti vlevo od pivotu 
• větší přemísti  vpravo od pivotu 

• obě části - rekurze 

Quick sort 

Merge sort 

• složitost O(n.log n) 
• potřebuje pomocnou paměť 
• vhodný k paralelizaci 
• princip 

• pokud jsou dva (nebo jeden) prvky 

• seřaď je 
• vrať se o úroveň výše 

• rozděl data na polovinu 
• na každou polovinu zavolej tuto funkci 
• spoj obě poloviny 

• poloviny jsou setříděné 
jejich spojení je tedy rychlé 

Merge sort 

• spojování seznamu 

• máme 2 setříděné seznamy 
• máme výstupní seznam 

• porovnáváme první hodnoty z obou seznamů 
• menší vložíme na první pozici výstupního seznamu 
• po vyprázdnění jednoho seznamu 

• kopírujeme zbytek dat z druhého 

Merge sort 

Shell sort 

• složitost O(n^(1.5)) 
• Modifikace Insert sortu 

• menší nároky na kód 

• menší nároky na zásobník 

• algoritmus: 

• zvolí se původní vzdálenost (např. 4) 

• začne se na prvním prvku 

• vezmou se prvky s danou vzdáleností 

• seřadí se pomocí insert sortu 

• posunujeme  se o jeden prvek 

• předchozí krok se opakuje 

• provedeme řazení vybraných prvků jako v minulém bodě 

• snížíme vzdálenost 

• opakujeme celý postup 

• poslední iterace -> klasický insert sort 

Shell sort 

• krok 

• celočíselné násobky čísla 2.2 
• začínáme od největšího možného kroku