Questão de Algoritmos e Estrutura de Dados — Algoritmos — CCV-UFC 2019
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq424765
Banca
CCV-UFC
Órgão
UFC
Ano
2019
Nível
Médio
Cargo
CCV - - Técnico de Tecnologia da Informação
Para realizar a ordenação de um vetor de inteiros contendo n números, foi utilizado um algoritmo de ordenação baseado na estratégia de dividir para conquistar e na divisão e ordenação recursiva das partes do vetor, obtendo um tempo de execução O(n log n). Qual das opções abaixo contém o algoritmo de ordenação descrito?
AShell Sort
BQuick Sort
CMerge Sort
DBucket Sort
EInsertion Sort
Revelar gabarito e comentário▾
GabaritoC — Merge Sort
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Análise de Algoritmos de Ordenação
Gabarito: letra C (Merge Sort). O Merge Sort é um algoritmo de ordenação que utiliza a estratégia de dividir para conquistar, dividindo recursivamente o vetor em metades, ordenando cada metade e depois intercalando-as, resultando em complexidade O(n log n) no pior caso. Essa descrição corresponde exatamente ao enunciado.
Vamos analisar cada alternativa:
Algoritmos de ordenação
1Dividir e conquistar
Merge Sort
Divide ao meio recursivamente
Ordena cada metade
Intercala (merge)
O(n log n) pior/médio/melhor caso
Quick Sort
Particiona por pivô
Pior caso O(n²)
2Outros
Shell Sort
Generalização do Insertion Sort
Pior caso O(n²)
Bucket Sort
Distribui em baldes
Média O(n)
Insertion Sort
Inserção incremental
Pior caso O(n²)
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Shell Sort. É uma generalização do Insertion Sort que usa gaps, mas não é baseado em dividir para conquistar nem possui complexidade O(n log n) garantida (no pior caso é O(n²)).
Alternativa B — ❌ Incorreta
Quick Sort. Embora use dividir e conquistar, seu pior caso é O(n²) — só o caso médio é O(n log n). O enunciado afirma "obtendo um tempo de execução O(n log n)" sem especificar caso, o que tornaria a afirmação imprecisa para o Quick Sort. Além disso, não há menção a particionamento, mas sim a "divisão e ordenação recursiva das partes", que é mais característico do Merge Sort.
Alternativa C — ✅ Correta ⟵ GABARITO
Merge Sort. Algoritmo clássico de dividir e conquistar: divide o vetor ao meio recursivamente, ordena cada metade e depois intercala (merge) as metades ordenadas. A complexidade é O(n log n) no pior, melhor e caso médio.
Alternativa D — ❌ Incorreta
Bucket Sort. Não é recursivo nem baseado em dividir para conquistar; distribui elementos em baldes e depois os ordena individualmente. Sua complexidade média é O(n), mas não O(n log n) em geral, e não se encaixa na descrição.
Alternativa E — ❌ Incorreta
Insertion Sort. É um algoritmo simples de ordenação por inserção, com complexidade O(n²) no pior caso, e não utiliza recursão nem dividir para conquistar.
PEGA ESSA DICA!
No estudo de algoritmos de ordenação, foque em compreender a estratégia (dividir e conquistar, incremental, etc.) e a complexidade de cada um. O Merge Sort é o único entre os listados que garante O(n log n) no pior caso e é puramente recursivo com divisão ao meio.