Fel tudnád sorolni a fő klasszikus algoritmusokat és jellemzőiket?

Fő klasszikus algoritmusok és jellemzőik:

• Rendezés:

  • Buborékrendezés (Bubble Sort) — egyszerű, de nem hatékony (O(n²)), tanulási célokra alkalmas.
  • Beszúrásos rendezés (Insertion Sort) — hatékony szinte rendezett adatok esetén.
  • Gyors rendezés (Quick Sort) — átlagosan gyors (O(n log n)), de a legrosszabb esetben O(n²).
  • Összefésülő rendezés (Merge Sort) — stabil, garantált O(n log n), extra memóriát igényel.

• Keresés:

  • Lineáris keresés — egyszerű, de lassú (O(n)).
  • Bináris keresés — gyors (O(log n)) rendezett tömbök esetén.

• Graf algoritmusok:

  • Mélységi keresés (DFS) és szélességi keresés (BFS) — graf bejárása.
  • Dijkstra algoritmusa — legrövidebb út keresése nem-negatív súlyú gráfban.

• Rekurzió és dinamikus programozás:

  • Olyan problémák megoldására használják, ahol az alproblémák átfednek, például Fibonacci-számok, hátizsák probléma.

• Greedy algoritmusok:

  • Helyben optimális döntéseket hoznak, például Kruskal algoritmusa a minimális feszítőfa számára.

Példa: Gyors rendezés C#-ban

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);
}