Questão de Algoritmos e Estrutura de Dados — Algoritmos — AOCP 2018

Algoritmos de ordenação

Gabarito: alternativa A. O QuickSort é um algoritmo eficiente (O(n log n) no caso médio), mas sua eficiência depende fortemente de uma boa escolha do pivô; uma má escolha pode levar ao pior caso O(n²). As demais alternativas contêm afirmações incorretas sobre outros algoritmos.

Alternativa A — ✅ Correta ⟵ GABARITO

O QuickSort realmente é eficiente em média, porém a escolha do pivô é crítica para evitar o pior caso. Técnicas como mediana de três ou pivô aleatório são comuns para mitigar esse problema.

Alternativa B — ❌ Incorreta

O algoritmo de ordenação por inserção (Insertion Sort) é simples de implementar e não é considerado "caro" (complexo). Seu desempenho é estável (mantém a ordem relativa de elementos iguais), mas a implementação é trivial, não "cara". A afirmação inverte os atributos.

Alternativa C — ❌ Incorreta

O HeapSort é eficiente em tempo (O(n log n)) e também eficiente em memória, pois ordena in-place, utilizando apenas espaço auxiliar constante (O(1)). Não é ineficiente em relação à memória; ao contrário, é um dos algoritmos mais econômicos nesse aspecto.

Alternativa D — ❌ Incorreta

O ShellSort não tem como principal desvantagem o fato de os dados estarem parcialmente ordenados; na verdade, ele se sai bem nesse cenário. Sua principal desvantagem é a complexidade de análise e a escolha dos gaps, e não o comportamento com dados parcialmente ordenados.

Alternativa E — ❌ Incorreta

O algoritmo de ordenação por seleção (Selection Sort) é simples de implementar (não é "cara"), mas seu desempenho não é estável. A ordenação por seleção geralmente não é estável (embora existam variações que a tornam estável, a implementação padrão é instável). A afirmativa está incorreta em ambos os pontos.

Gabarito: letra A.