Zhrnutie na Radiace a vyhľadávacie algoritmy

## Triediace a vyhľadávacie algoritmy V informatike sú algoritmy základnými stavebnými kameňmi pre riešenie problémov. Sú to presne definované postupy alebo súbory inštrukcií, ktoré krok za krokom vedú k vyriešeniu určitej úlohy. Kľúčovou vlastnosťou algoritmov je ich **deterministickosť** (pre rovnaký vstup vždy produkujú rovnaký výstup), **konečnosť** (musia skončiť v konečnom čase) a **efektívnosť** (mali by využívať zdroje, ako je čas a pamäť, čo najoptimálnejšie). Medzi najčastejšie a najdôležitejšie typy algoritmov patria triediace a vyhľadávacie algoritmy. ### Triediace algoritmy Triediace algoritmy slúžia na usporiadanie prvkov v zozname (napríklad čísel alebo textových reťazcov) do určitého poradia, najčastejšie vzostupného alebo zostupného. Triedenie je základnou operáciou, ktorá zlepšuje efektívnosť mnohých ďalších algoritmov. Did you know, že triedenie dát je jednou z najčastejšie vykonávaných operácií v informatike a databázových systémoch, pričom optimalizované triediace algoritmy sú kľúčové pre celkový výkon softvéru? ### Časová zložitosť a O-notácia Efektívnosť algoritmu sa často meria jeho časovou zložitosťou, ktorá popisuje, ako sa doba behu algoritmu mení s rastúcou veľkosťou vstupu. Na vyjadrenie tejto závislosti sa používa tzv. **O-notácia (Big O notation)**, ktorá udáva hornú hranicu rastu funkcie, teda najhorší možný scenár výkonu algoritmu. Ignoruje konštantné faktory a nižšie rády, sústrediac sa na dominantný člen, ktorý určuje správanie algoritmu pre veľké vstupy. > **O-notácia (Big O notation)**: Matematické vyjadrenie hornej hranice rastu funkcie, ktoré popisuje najhorší možný scenár výkonu algoritmu s rastúcou veľkosťou vstupu. Ignoruje konštantné faktory a nižšie rády. * **$O(1)$ – Konštantná zložitosť:** Doba behu algoritmu je nezávislá od veľkosti vstupu. Príkladom je prístup k prvku v poli pomocou indexu. * **$O(\log n)$ – Logaritmická zložitosť:** Doba behu rastie veľmi pomaly s veľkosťou vstupu. Typickým príkladom je binárne vyhľadávanie, kde sa v každom kroku problém zmenší na polovicu. * **$O(n)$ – Lineárna zložitosť:** Doba behu rastie priamo úmerne s veľkosťou vstupu. Príkladom je lineárne vyhľadávanie alebo prechádzanie všetkých prvkov v zozname. * **$O(n \log n)$ – Lineárno-logaritmická zložitosť:** Často sa vyskytuje pri efektívnych triediacich algoritmoch, ako je rýchle triedenie alebo triedenie zlučovaním. Je výrazne lepšia ako kvadratická zložitosť. * **$O(n^2)$ – Kvadratická zložitosť:** Doba behu rastie s druhou mocninou veľkosti vstupu. Typické pre jednoduché triediace algoritmy, ako je bublinkové triedenie alebo triedenie výberom. Pre veľké vstupy sa stáva veľmi neefektívnou. Pochopenie O-notácie je kľúčové pre výber správneho algoritmu pre danú úlohu, najmä pri práci s rozsiahlymi dátovými súbormi. #### Bublinkové triedenie (Bubble Sort) Bublinkové triedenie je jednoduchý triediaci algoritmus, ktorý opakovane prechádza zoznamom, porovnáva susedné prvky a vymieňa ich, ak sú v nesprávnom poradí. Tento proces sa opakuje, kým nie sú všetky prvky usporiadané. Väčšie prvky sa postupne „bublinkujú“ na koniec zoznamu. **Postup:** 1. Prejdite zoznam od začiatku do konca. 2. Pre každý pár susedných prvkov (napr. prvok na pozícii $i$ a $i+1$): * Ak je prvok na pozícii $i$ väčší ako prvok na pozícii $i+1$, vymeňte ich. 3. Opakujte celý prechod zoznamom, kým sa v jednom prechode neurobí žiadna výmena, čo signalizuje, že zoznam je usporiadaný. **Časová zložitosť:** $O(n^2)$ v najhoršom aj priemernom prípade. Je to jeden z najmenej efektívnych triediacich algoritmov pre veľké vstupy. **Príklad:** Triedenie zoznamu $[5, 1, 4, 2, 8]$ vzostupne. * **1. prechod:** * $(5, 1) \to [1, 5, 4, 2, 8]$ * $(5, 4) \to [1, 4, 5, 2, 8]$ * $(5, 2) \to [1, 4, 2, 5, 8]$ * $(5, 8) \to [1, 4, 2, 5, 8]$ * **2. prechod:** * $(1, 4) \to [1, 4, 2, 5, 8]$ * $(4, 2) \to [1, 2, 4, 5, 8]$ * $(4, 5) \to [1, 2, 4, 5, 8]$ * $(5, 8) \to [1,