04 - Searching and Sorting

Zhrnutie prednášky

Prednáška nadväzuje na štruktúrované údajové typy a ukazuje, ako nad poľami štruktúr vykonávať vyhľadávanie a triedenie. Najprv sa v jazyku C implementuje lineárne vyhľadávanie podľa priezviska, ktoré prechádza pole od začiatku a vracia index nájdeného prvku alebo -1. Následne sa lineárne a binárne vyhľadávanie porovnáva podľa zložitosti: lineárne je O(n), binárne O(log₂ n), no vyžaduje usporiadané pole a funguje princípom rozdeľuj a panuj, podobne ako hra na hádanie čísla. Zo štandardnej knižnice stdlib.h sa predstavujú funkcie bsearch a qsort, pričom qsort berie adresu poľa, počet prvkov, veľkosť prvku a komparátor, ktorý porovnáva dva prvky. Na konci sa začína tvorba vlastnej komparačnej funkcie pre štruktúru osoby.

• - Lineárne vyhľadávanie prechádza pole prvok po prvku a vracia index alebo -1, ak prvok nenájde.
• - Vyhľadávať možno podľa ľubovoľného poľa štruktúry, napríklad priezviska, pomocou strcmp.
• - Lineárne vyhľadávanie má zložitosť O(n), binárne O(log₂ n); rozdiel rastie s počtom prvkov.
• - Binárne vyhľadávanie vyžaduje zotriedené pole a opakovane delí interval na polovice.
• - Štandardná knižnica stdlib.h poskytuje funkcie bsearch a qsort.
• - Funkcia qsort prijíma base, počet prvkov, veľkosť prvku a komparátor.
• - Komparátor dostane adresy dvoch prvkov a vráti zápornú hodnotu, nulu alebo kladnú hodnotu podľa ich poradia.

Zhrnutie pripravené s pomocou AI z prepisu videa.