07_razeni
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
• maximum se na konec dostane v jednom cyklu
• malé hodnoty se doleva posunují pomalu
• v jednom cyklu posun maximálně o jednu pozici
Bubble sort
Shaker sort
• vychází z bubble sortu
• princip
• netřídí jen jedním směrem
• směr průchodu se po každém cyklu mění
• obousměrný bubble sort
• složitost O(n^2)
• z praktického hlediska neefektivní
• odstraňuje některé nedostatky bubble sortu
• nedojde k výraznému zlepšení
Comb sort
• vychází z bubble sortu
• princip
• zavádí se snižující přírůstek
• volí se různá vzdálenost mezi porovnávanými prvky
• začne se velkou vzdálenosti (půl intervalu)
• postupně se vzdálenost zkracuje (faktor 1.3) až k jedné
• v poslední fázi degraduje na klasický bubble sort
• složitost: O(n) až O(n^2)
Select sort
• řazení výběrem
• pole rozdělíme
• seřazená část
• neseřazená část
• princip
• vybíráme extrém z neseřazené části
• vyměníme s prvním prvkem v neseřazené čísti
• zmenšíme neseřazenou část
• složitost O(n^2)
• konstantní paměťová složitost
Select sort
Nesetříděná část
Prvky se vybírají postupně
Setříděná část
Prvky vkládané na místo
podle velikosti
Double select sort
• vylepšení algoritmu select sort
• současně hledáme oba extrémy
• setříděné části vznikají na obou stranách
Insert sort
• řazení vkládáním
• pole rozdělíme
• seřazená část
• neseřazená část
• princip
• bereme prvky z neseřazené části
• vkládáme je na místo v seřazené části
• složitost O(n^2)
• u téměř seřazeného pole se blížíme k O(n)
Insert sort
Nesetříděná část
Prvky se vybírají postupně
Setříděná část
Prvky vkládané na místo
podle velikosti
Quick sort