Questão de Algoritmos e Estrutura de Dados — Algoritmos de Ordenação — INSTITUTO AOCP 2023
Algoritmos e Estrutura de Dados›Algoritmos de Ordenação
Código
qq971019
Banca
INSTITUTO AOCP
Órgão
IF-MA
Ano
2023
Nível
Superior
Cargo
Analista De Tecnologia Da Informação - Desenvolvimento De Sistemas
Métodos de ordenação são algoritmos usados para organizar elementos de uma sequência em uma ordem específica. Qual método de ordenação tem complexidade de tempo médio O(n log n) e utiliza a técnica de dividir e conquistar?
ABubble sort.
BSelection sort.
CInsertion sort.
DQuick sort.
EMerge sort.
Revelar gabarito e comentário▾
GabaritoE — 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”.
Algoritmos de ordenação
Gabarito: letra E. O Merge sort (ordenação por intercalação) é o único algoritmo entre as opções que possui complexidade de tempo O(n log n) em todos os casos (médio, pior e melhor) e utiliza a técnica de dividir e conquistar de forma clássica, dividindo sempre o vetor ao meio. Embora o Quick sort também tenha complexidade média O(n log n), seu pior caso é O(n²) e sua divisão pode ser desbalanceada, não sendo considerado o exemplo canônico de "dividir e conquistar" para a banca.
A questão cobra o conhecimento das complexidades e características dos principais métodos de ordenação. Vamos analisar cada alternativa:
Algoritmos de ordenação
1O(n²)
Bubble sort (troca)
Selection sort (seleção)
Insertion sort (inserção)
2O(n log n) — dividir e conquistar
Merge sort (intercalação)
Divide ao meio
O(n log n) em todos os casos
Quick sort (pivô)
Média O(n log n)
Pior caso O(n²)
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Bubble sort possui complexidade O(n²) tanto no pior quanto no caso médio, e não utiliza a técnica de dividir e conquistar. É um algoritmo simples de troca, mas ineficiente para grandes entradas.
Alternativa B — ❌ Incorreta
Selection sort também opera em O(n²) em todos os casos, selecionando o menor elemento a cada iteração. Não se baseia em divisão e conquista.
Alternativa C — ❌ Incorreta
Insertion sort tem complexidade O(n²) no pior caso e médio, embora seja eficiente para pequenas entradas ou sequências parcialmente ordenadas. Não usa dividir e conquistar.
Alternativa D — ❌ Incorreta
Quick sort tem complexidade média O(n log n) e utiliza uma abordagem de divisão por pivô, que é uma forma de dividir e conquistar. No entanto, seu pior caso é O(n²) (quando o pivô é mal escolhido), e a divisão não é garantidamente balanceada — diferentemente do merge sort, que sempre divide a sequência ao meio. Por isso, a banca considera o merge sort como a resposta esperada para a pergunta sobre "método de ordenação que tem complexidade de tempo médio O(n log n) e utiliza a técnica de dividir e conquistar".
Alternativa E — ✅ Correta ⟵ GABARITO
Merge sort é o algoritmo clássico de ordenação por intercalação. Ele divide recursivamente o vetor ao meio até que reste apenas um elemento (divisão) e depois intercala as partes ordenadas (conquista). Sua complexidade é O(n log n) em todos os casos (médio, pior e melhor), sendo estável e amplamente utilizado.
PEGA ESSA DICA!
Para memorizar as complexidades, foque na tabela abaixo: