Can you name the main classic algorithms and their features?

Main classical algorithms and their features:

• Sorting:

  • Bubble Sort — simple but inefficient (O(n²)), suitable for learning.
  • Insertion Sort — effective for nearly sorted data.
  • Quick Sort — fast on average (O(n log n)), but worst case O(n²).
  • Merge Sort — stable, guaranteed O(n log n), requires additional memory.

• Searching:

  • Linear Search — simple but slow (O(n)).
  • Binary Search — fast (O(log n)) for sorted arrays.

• Graph algorithms:

  • Depth-First Search (DFS) and Breadth-First Search (BFS) — graph traversal.
  • Dijkstra's Algorithm — finds the shortest path in a graph with non-negative weights.

• Recursion and dynamic programming:

  • Used for solving problems with overlapping subproblems, such as Fibonacci number calculation, knapsack problem.

• Greedy algorithms:

  • Make locally optimal choices, e.g., Kruskal's algorithm for minimum spanning tree.

Example: Quick Sort in 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);
}