Mohol by si uviesť hlavné klasické algoritmy a ich vlastnosti?

Hlavné klasické algoritmy a ich vlastnosti:

• Zoradenie:

  • Bubble Sort — jednoduchý, ale neefektívny (O(n²)), vhodný na učenie.
  • Vkladanie (Insertion Sort) — efektívny pre takmer zoradené údaje.
  • Rýchle zoradenie (Quick Sort) — priemerná rýchlosť (O(n log n)), ale v najhoršom prípade O(n²).
  • Zlučovacie zoradenie (Merge Sort) — stabilné, garantované O(n log n), vyžaduje dodatočnú pamäť.

• Hľadanie:

  • Lineárne hľadanie — jednoduché, ale pomalé (O(n)).
  • Binárne hľadanie — rýchle (O(log n)) pre zoradené polia.

• Algoritmy na grafoch:

  • Hlboké vyhľadávanie (DFS) a šírkové vyhľadávanie (BFS) — prechádzanie grafu.
  • Dijkstrov algoritmus — nájdenie najkratšej cesty v grafe s nenegatívnymi váhami.

• Rekurzia a dynamické programovanie:

  • Používajú sa na riešenie problémov s prekrývajúcimi sa podproblémami, napríklad Fibonacciho čísla, problém batohu.

• Greedy algoritmy:

  • Robia lokálne optimálne rozhodnutia, napríklad Kruskalov algoritmus pre minimálnu kostru.

Príklad: Rýchle zoradenie v C#

void QuickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[(left + right) / 2];
    int i = left, j = right;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
            i++; j--;
        }
    }
    QuickSort(arr, left, j);
    QuickSort(arr, i, right);
}