Algoritmos de ordenação híbridos
Gabarito: letra A. Heapsort é apresentado pela banca como o algoritmo que combina o melhor do merge sort (intercalação) com o melhor do insertion sort (inserção), embora classicamente o Timsort seja o híbrido conhecido. Heapsort utiliza uma estrutura de heap para ordenação no lugar com complexidade O(n log n), incorporando eficiência de merge (logarítmica) e simplicidade de inserção (in-place).
A questão testa o conhecimento sobre algoritmos de ordenação e suas características. Vamos analisar cada alternativa:
Alternativa A — ✅ Correta ⟵ GABARITO
Heapsort é indicado pela banca como o algoritmo que combina as vantagens do merge sort (eficiência O(n log n)) e do insertion sort (ordenação no lugar e bom desempenho para pequenas entradas). Embora na prática o Heapsort não seja um híbrido, a banca considera essa definição.
Alternativa B — ❌ Incorreta
Quicksort tem complexidade O(n²) no pior caso e não é o resultado da combinação de merge com insertion. Ele utiliza particionamento.
Alternativa C — ❌ Incorreta
“Tempo linear” é uma classe de complexidade, não um algoritmo específico. Não atende ao enunciado.
Alternativa D — ❌ Incorreta
Fila de prioridades é uma estrutura de dados, não um algoritmo de ordenação completo. Embora heapsort use heap (implementação de fila de prioridades), essa opção não representa o algoritmo que combina merge e insertion.
Alternativa E — ❌ Incorreta
Particionamento balanceado é uma técnica usada em merge sort e quicksort, mas não é um algoritmo de ordenação nomeado.
Gabarito: letra A