Можеш ли да назовеш основните класически алгоритми и техните характеристики?

Основни класически алгоритми и техните характеристики:

• Сортиране:

  • Пуканково сортиране (Bubble Sort) — просто, но неефективно (O(n²)), подходящо за обучение.
  • Вмъкване (Insertion Sort) — ефективно за почти сортирани данни.
  • Бързо сортиране (Quick Sort) — бързо средно (O(n log n)), но в най-лошия случай O(n²).
  • Обединително сортиране (Merge Sort) — стабилно, гарантирано O(n log n), изисква допълнителна памет.

• Търсене:

  • Линейно търсене — просто, но бавно (O(n)).
  • Бинарно търсене — бързо (O(log n)) за сортирани масиви.

• Алгоритми за графи:

  • Търсене в дълбочина (DFS) и търсене в ширина (BFS) — обход на граф.
  • Алгоритъм на Дейкстра — намиране на най-краткия път в граф с неотрицателни тегла.

• Рекурсия и динамично програмиране:

  • Използват се за решаване на задачи с припокриващи се подзадачи, например изчисляване на числа на Фибоначи, задачи за раница.

• Жадни алгоритми:

  • Вземат локално оптимални решения, например алгоритъм на Крускал за минимално покриващо дърво.

Пример: Бързо сортиране на 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);
}