6.       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