Questão de Algoritmos e Estrutura de Dados — Algoritmos — COMVEST UFAM 2023
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq846317
Banca
COMVEST UFAM
Órgão
UFAM
Ano
2023
Nível
Médio
Cargo
COMVEST - - Técnico em Tecnologia da Informação
Sobre o algoritmo de ordenação Merge Sort, ou Ordenação por Mistura, é CORRETO afirmar que:
Aé mais lento que o Método da Bolha (Bubble Sort) quando empregado sobre uma grande quantidade de dados.
Bé mais lento que o Método da Seleção (Selection Sort) quando empregado sobre uma grande quantidade de dados.
Cpara pequenos conjuntos, o Merge Sort é sempre mais eficiente que os demais métodos.
Dé o único algoritmo de ordenação na categoria Divisão e Conquista.
Eusa a técnica de ordenação por comparação do tipo dividir-para-conquistar.
Revelar gabarito e comentário▾
GabaritoE — usa a técnica de ordenação por comparação do tipo dividir-para-conquistar.
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”.
Merge Sort (Ordenação por Mistura)
Gabarito: letra E. O Merge Sort é um algoritmo de ordenação por comparação que aplica a técnica de dividir-para-conquistar: divide o vetor em duas metades, ordena cada metade recursivamente e depois intercala (merge) as duas metades ordenadas. Essa é a definição central do algoritmo.
A banca testa o conhecimento básico sobre o Merge Sort e sua classificação. Vamos analisar cada alternativa:
Alternativa
Afirmação
Análise
Complexidade/Contexto
Veredito
A
Merge Sort é mais lento que Bubble Sort para grandes dados
Falso: Merge Sort O(n log n) vs Bubble Sort O(n²)
Merge Sort é muito mais rápido para grandes entradas
❌ Incorreta
B
Merge Sort é mais lento que Selection Sort para grandes dados
Falso: ambos O(n²) no pior caso, mas Merge Sort O(n log n) é superior
Selection Sort também é O(n²)
❌ Incorreta
C
Merge Sort é sempre mais eficiente para pequenos conjuntos
Falso: Insertion Sort pode ser mais rápido para <10-20 elementos
Overhead de recursão e merge prejudica em entradas pequenas
❌ Incorreta
D
Merge Sort é o único algoritmo de ordenação Divisão e Conquista
Falso: Quicksort, Stooge Sort e outros também se enquadram
Termo absoluto "único" é a pegadinha
❌ Incorreta
E
Merge Sort usa técnica dividir-para-conquistar por comparação
Verdadeiro: divide vetor, ordena recursivamente, intercala
Definição central do algoritmo
✅ Correta
Merge Sort: Técnica (Divisão e conquista, Ordenação por comparação); Complexidade (O(n log n) — pior caso, Melhor que O(n²)); Funcionamento (Divide vetor em metades, Ordena recursivamente, Intercala (merge)); Limitação (Overhead para conjuntos pequenos)
Alternativa A — ❌ Incorreta
Afirma que o Merge Sort é mais lento que o Bubble Sort para grandes quantidades de dados. Na verdade, o Merge Sort tem complexidade O(n log n) no pior caso, enquanto o Bubble Sort é O(n²). Para grandes entradas, o Merge Sort é muito mais rápido. Portanto, a afirmação é falsa.
Alternativa B — ❌ Incorreta
Afirma que o Merge Sort é mais lento que o Selection Sort para grandes quantidades de dados. O Selection Sort também é O(n²), então, assim como na alternativa A, o Merge Sort é mais eficiente para entradas grandes. Afirmação falsa.
Alternativa C — ❌ Incorreta
Diz que para pequenos conjuntos o Merge Sort é sempre mais eficiente que os demais. Na prática, para conjuntos muito pequenos (ex.: menos de 10-20 elementos), algoritmos simples como Insertion Sort podem ser mais rápidos devido à baixa sobrecarga de chamadas recursivas e merges. O Merge Sort tem um overhead que o torna não ideal para entradas muito pequenas. Logo, a afirmação é falsa.
Alternativa D — ❌ Incorreta
Afirma que o Merge Sort é o único algoritmo de ordenação na categoria Divisão e Conquista. Isso é falso: o Quicksort também é um algoritmo de divisão e conquista (embora com uma abordagem diferente de partição). Além disso, outros algoritmos como o Stooge Sort e até mesmo versões recursivas de ordenação por inserção (embora não práticas) também se enquadram. O Merge Sort não é o único.
NÃO CAIA NESSA!
Cuidado com termos absolutos como "único". A banca explora a generalização indevida. Lembre-se: Quicksort também é divisão e conquista!
Alternativa E — ✅ Correta ⟵ GABARITO
Afirma corretamente que o Merge Sort usa a técnica de ordenação por comparação do tipo dividir-para-conquistar (ou divisão e conquista). Essa é a essência do algoritmo: dividir o problema em subproblemas menores (metades), resolver recursivamente e combinar (merge). Portanto, alternativa correta.
Conclusão: A única afirmação correta sobre o Merge Sort é a letra E. As demais ou contradizem a complexidade conhecida ou contêm generalizações incorretas.