6. Vizuální a objektově orientované programování, základní pojmy a principy

Třídící algoritmy – principy třídění, rekurze – vzájemná, přímá

Třídící algoritmy

BUBLLE SORT
Mění se a porovnávají čísla vedle sebe
Když nesouhlasí, první se prohodí
Dělá se n-1

Princip

Tato třídící metoda je ze všech uvedených metod nejjednodušší, ale také nejpomalejší. Její princip spočívá v jednoduché záměně dvou sousedních prvků, pokud nevyhovují dané podmínce. Procedura obsahuje dva do sebe vnořené cykly, vnější zajišťuje zmenšování počtu prvků, které stále nejsou setříděny a vnitřní cyklus zajišťuje vlastní výměny dvou prvků v jednom průchodu posloupností.

INSERT SORT
Třídění vkládáním

Princip

Tato metoda je založena na principu vkládání prvku na jeho správné místo v posloupnosti. Jak si můžete porovnat předchozí výpisy metod s výpisem této metody, používá pole o velikostí ne 10, ale 11 prvků, počínaje již nultým prvkem. Tento se v celé posloupnosti využívá jako pomocný prvek a samotná posloupnosti jej do sebe nezahrnuje.

SELECT SORT
Vybereme nejmenší (největší) číslo a porovnáváme s prvním, pokud sedí velikost, promění se prvky mezi sebou

Princip

Metoda pracuje na principu nalezení minimálního prvku v nesetříděné části posloupností a jeho zařazení na konec již setříděné posloupnosti. Metoda prochází celou nesetříděnou část posloupnosti a hledá nejmenší prvek. Až jej nalezne, vrátí se na konec již setříděné části posloupnosti a tento nejmenší prvek zde uloží. Tyto dvě činnosti vykonává do té doby, dokud neprojde celou posloupnost a nesetřídí ji.

Rekurze

V imperativním programování rekurze představuje opakované vnořené volání stejné funkce (podprogramu), v takovém případě se hovoří o rekurzivní funkci. Nedílnou součástí rekurzivní funkce musí být ukončující podmínka určující, kdy se má vnořování zastavit. Jelikož bývá nejčastějším zdrojem chyb, je třeba ji navrhnout dostatečně robustním způsobem a prověřit veškeré možné stavy.

Pro uplatnění rekurzivních algoritmů je zapotřebí, aby programovací jazyk umožňoval volání podprogramu ještě před ukončením jeho předchozího volání.

Po každém kroku volání sebe sama musí dojít ke zjednodušení problému. Pokud nenastane koncová situace, provede se rekurzivní krok.

Každý algoritmus využívající rekurzi lze přepsat do nerekurzivního tvaru při použití zásobníku nebo jiné paměťové struktury.

– způsob volání procedur a funkcí

– takové volání, které nastane dřív, než předchozí volání skončí

– 2 typy – PŘÍMÁ, VZÁJEMNÁ

PŘÍMÁ REKURZE
Pokud procedura nebo funkce volá sama sebe

VZÁJEMNÁ REKURZE
Když v jedné proceduře voláme jinou proceduru a v druhé voláme zaes první proceduru
Může být víc procedur a funkcí
Podmínka rekurze –
kdy vzájemné volání podprogramů vytvoří „kruh“. Např. v příkazové části funkceA je volána funkce B, ve funkci B voláme funkci C, která volá funkci A.

Výhoda rekurze

jednoduchost
přehlednost programu

Nevýhoda rekurze

Časová náročnost
Paměťová náročnost – vymezování většího počtu paměťového místa