Třídicí algoritmy

Bubble sort

• Řazení záměnou.
• Postupné porovnávání dvou sousedních prvků a jejich záměně v případě, že jejich pořadí neodpovídá hodnotám.

 

Insertion sort

• Založen na postupném zařazování druhého, třetího až n-tého prvku na odpovídající místo v již setříděné podposloupnosti.
• Každý prvek je porovnáván s prvky předchozími, které už jsou uspořádány odpovídajícím způsobem.
• Prvek a[i] zařadíme tak, že odzadu prohlížíme úsek, který je již seřazen a hledáme místo, kam prvek hodnotou patří.
• Přitom vždy porovnávaný prvek, pokud jeho pořadí nesouhlasí, posuneme o jedno místo dozadu.

 

Selection sort

• Řazení pole výběrem nejmenšího nebo největšího prvku.
• V prohledávané zóně nalezneme nejmenší nebo největší prvek.
• Tento prvek se zamění s prvním prvkem v prohledávané zóně.
• V dalším kroku prohledáváme celé pole bez prvního prvku, čímž se nám prohledávaná zóna zmenší o jedno.
• Tento postup opakujeme n-1-krát – poté je celé pole uspořádané.

 

Rekurze

Rekurzivním voláním procedury či funkce se rozumí takové volání, které nastane dříve než předchozí bylo dokončeno.

• Přímá rekurze.
  • Nastává, pokud procedura či funkce volá sama sebe. V bloku příkazů této procedury nebo funkce je příkaz volání stejné procedury nebo funkce.

• Nepřímá (vzájemná) rekurze.
  • Nastává, pokud se minimálně dvě procedury či funkce, volají vzájemně („v kruhu“). Například funkce A volá funkci B, která ke svému provedení potřebuje funkci A.

 

Dynamické datové struktury

• Statická datová struktura.
  • Datová strukturam, jejíž rozsah se během výpočtu nemění.
  • Statické proměnné jsou zavedené deklarací.
  • Každá proměnná má své jméno.

• Dynamická datová struktura
  • Nemají pevný rozsah (může se měnit).
  • Nejsou vytvořené deklarací a označené identifikátory.
  • Jsou vytvořeny v průběhu programu pomocí speciálního příkazu.
  • Pro identifikaci dynamické proměnné se používá datový typ UKAZATEL.
  • Obsahuje adresu umístění proměnné v paměti.

 

Typ ukazatel

Chceme-li pracovat v programu s dynamickými proměnnými postupujeme takto:

• Definujeme typ této proměnné.
• Deklarujeme proměnnou typu UKAZATEL.

type U = ^T;

T = typ;

var p: U;

Zápis definuje typ U jako množinu adres, které ukazují na prvky typu T. U se nazývá typ ukazatel a říkáme, že je vázán na typ T. p je proměnná typu ukazatel, jejími hodnotami jsou adresy dynamických proměnných typu T. Každá proměnná typu ukazatel může obsahovat nil, která neukazuje na žádný prvek. Proměnná typu T, na kterou ukazuje proměnná p, se označuje p^.

 

Procedury NEW a DISPOSE

Dynamické proměnné vznikají na základě příkazu NEW. Je-li proměnná p typu ukazatel na T, pak NEW(p); vytvoří novou dynamickou proměnnou typu T a ukazatel na tuto proměnnou (adresu místa v paměti) do proměnné p. Uvolnění místa se provede příkazem DISPOSE(p). Dynamické proměnné slouží především ke konstrukci složitějších dynamických struktur, např. zásobníků, front, lineárních seznamů a binárních stromů.

 

Zásobník

Zásobníkem rozumíme takovou dynamickou datovou strukturu, z níž se prvky vybírají v opačném pořadí než v jakém se do ní vkládají. Vybíráme tedy vždy poslední vložený prvek. Jedná se o typ LIFO tzn. last in, first out (v češtině poslední dovnitř, první ven).

Pro zásobník můžeme definovat tyto základní operace:

• Vytvoření prázdného zásobníku.
• Vložení prvku na vrchol zásobníku.
• Odebrání prvku z vrcholu zásobníku.
• Testování prázdnosti zásobníku.

Ukazatel je pouze 1 a to na “hrdlo“ zásobníku.

 

Fronta

Fronta je dynamická datová struktura podobná zásobníku, rozdíl je pouze v tom, že prvky se z fronty odebírají v tom pořadí, v jakém se do fronty vkládají. Jedná se o typ FIFO tzn. first in, first out (v češtině první dovnitř, první ven).

Pro frontu můžeme definovat tyto operace

• Vytvoření prázdné fronty.
• Vložení prvku na konec fronty.
• Odebrání prvku ze začátku fronty.
• Test prázdnosti fronty.

Ukazatelé jsou 2 a to na začátek a konec fronty.

 

Lineárně zřetězený seznam

• Datová struktura, uchovávající posloupnost proměnného počtu prvků téhož typu.
• Uložení prvku do seznamu a odebrání prvku ze seznamu je možné aplikovat v kterémkoliv místě seznamu.
• Obsahuje 2 ukazatele a to na aktuální prvek a na začátek nebo konec seznamu.

 

Binární strom

• Z dynamických proměnných můžeme vytvořit složitější struktury, ve kterých může mít každý prvek více následovníků.
• Nejčastějším typem těchto struktur jsou tzv. binární stromy.
• Binární strom se skládá z uzlů, které obsahují nějakou hodnotu a 2 ukazatele.
  • 1. na levého následovníka.
  • 2. na pravého následovníka.
• Uzel, který nemá předchůdce, se nazývá kořen.
• Uzly, které nemají následovníka, se nazývají listy.
• Pokud uzel nemá příslušného následovníka, tak daný ukazatel obsahuje hodnotu nil.