Poderia nomear os principais algoritmos clássicos e suas características?

Algoritmos clássicos principais e suas características:

• Ordenação:

  • Ordenação de bolha (Bubble Sort) — simples, mas ineficiente (O(n²)), adequado para aprendizagem.
  • Ordenação por inserção (Insertion Sort) — eficiente para dados quase ordenados.
  • Ordenação rápida (Quick Sort) — rápida em média (O(n log n)), mas no pior caso O(n²).
  • Ordenação por fusão (Merge Sort) — estável, garantido O(n log n), requer memória adicional.

• Busca:

  • Busca linear — simples, mas lenta (O(n)).
  • Busca binária — rápida (O(log n)) para arrays ordenados.

• Algoritmos em grafos:

  • Busca em profundidade (DFS) e busca em largura (BFS) — percurso do grafo.
  • Algoritmo de Dijkstra — busca do caminho mais curto em um grafo com pesos não negativos.

• Recursão e programação dinâmica:

  • Usados para resolver problemas com subproblemas sobrepostos, por exemplo, cálculo de números de Fibonacci, problemas de mochila.

• Algoritmos gananciosos:

  • Tomam decisões localmente ótimas, por exemplo, o algoritmo de Kruskal para a árvore geradora mínima.

Exemplo: Ordenação rápida em 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);
}