Vai jūs varētu uzskaitīt galvenos klasiskos algoritmus un to īpašības?

Galvenie klasiskie algoritmi un to īpašības:

• Kārtošana:

  • Burbuļa kārtošana (Bubble Sort) — vienkārša, bet neefektīva (O(n²)), piemērota mācībām.
  • Ievietošanas kārtošana (Insertion Sort) — efektīva gandrīz kārtotos datos.
  • Ātrā kārtošana (Quick Sort) — vidēji ātra (O(n log n)), bet sliktākajā gadījumā O(n²).
  • Apvienošanas kārtošana (Merge Sort) — stabila, garantēta O(n log n), prasa papildu atmiņu.

• Meklēšana:

  • Līnijas meklēšana — vienkārša, bet lēna (O(n)).
  • Divkāršā meklēšana — ātra (O(log n)) kārtotos masīvos.

• Grafu algoritmi:

  • Dziļuma pirmkoda meklēšana (DFS) un platuma pirmkoda meklēšana (BFS) — grafu apmeklējums.
  • Dijkstra algoritms — meklē visīsāko ceļu grafā ar pozitīviem svariem.

• Rekursija un dinamiskā programmēšana:

  • Izmanto, lai risinātu problēmas ar pārklājošiem apakšproblemiem, piemēram, Fibonacci skaitļu aprēķinu, muguras soma problēmu.

• Greedy algoritmi:

  • Pieņem vietējo optimālo lēmumu, piemēram, Kruskala algoritms minimālajam pārklājošajam kokam.

Piemērs: Ātrā kārtošana 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);
}