07_razeni

• algoritmus má dvě porovnání 

• konce pole 
• nalezení hodnoty 
• zjednodušení? 

• Na konec pole se dá hledaná hodnota 
• zarážka (sequential search sentinel) 

Vyhledávání binární 

• vyžaduje setříděné pole 
• nejhorší O(log2 n)  
• vyhledávání pomocí metody půlení intervalu 

Vyhledávání interpolační 

• vyžaduje setříděné pole 
• podobné binárnímu 
• pomáháme si znalostí 

• odhadem pozice 
• na základě znalosti rozložení hodnot 

• O(log (log n) ) 

• hledání jmen 

• určíme si četnost zastoupení jednotlivých písmen 
• z rozložení určíme počátek, krok 

• pomocná tabulka – pozice prvních jmen dle písmena 

• hledání výšek osob 

Řazení 

• data 

• jednoduchá (int, float…) 
• složitá (záznamy v databázi, vektor, komplexní číslo ) 

• směr řazení 

• sestupně 
• vzestupně 

• stanovení porovnávací funkce 

• vrací 

• -1 – první je před druhým 
•  0 – parametry stejné/nezáleží na pořadí 
• +1 – první je za druhým 

Řazení 

• dvojce hodnota – klíč 

• řazení pomocí klíčů 
• stabilní řazení 

• zachovává pořadí položek se stejným klíčem 
• hodnota 0 porovnávací fce 

 nechat prvky jak jsou 

• prostor pro řazení 

• stejný 
• pomocný 

paměťová náročnost 

Řazení 

• testy pro ověření kvality a času řazení 

• správně seřazená data 
• opačně seřazená data 
• téměř seřazená data správně 
• téměř seřazená data opačně 
• náhodná data 

• přirozený algoritmus 

• vyšší rychlost pro částečně seřazená data 

Bubble sort 

• řazení probubláním 
• princip 

• porovnáváme sousedy a jejich případná výměna 

• složitost O(n^2) 
• u téměř seřazeného pole se blížíme k O(n) 
• velké hodnoty zleva probublají rychle