Questão de Algoritmos e Estrutura de Dados — Algoritmos — Instituto Consulplan 2023
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq984867
Banca
Instituto Consulplan
Órgão
MPE-BA
Ano
2023
Nível
Superior
Cargo
Analista Técnico – Análise de Sistemas
Algoritmos de ordenação são responsáveis por ordenar elementos de uma estrutura de dados de forma completa ou parcial. Sobre a complexidade dos algoritmos de ordenação, assinale, a seguir, o algoritmo de ordenação que, no pior caso, tem complexidade igual a O(n log n).
AQuick sort.
BMerge sort.
CBubble sort.
DInsertion sort.
ESelection sort.
Revelar gabarito e comentário▾
GabaritoB — 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: complexidade no pior caso
Gabarito: letra B — Merge sort. A questão cobra o conhecimento da complexidade assintótica dos principais algoritmos de ordenação no pior cenário. Apenas o Merge sort garante O(n log n) em qualquer caso; os demais (Quick sort, Bubble sort, Insertion sort e Selection sort) apresentam complexidade O(n²) no pior caso.
A banca explora a pegadinha clássica: o Quick sort tem complexidade média O(n log n), mas seu pior caso é O(n²), ao contrário do Merge sort, que mantém O(n log n) mesmo no pior cenário.
NÃO CAIA NESSA!
Trocar a complexidade média do Quick sort (O(n log n)) pela complexidade do pior caso. O Quick sort pode ser O(n²) se a escolha do pivô for desfavorável; apenas o Merge sort é garantidamente O(n log n) em todas as situações.
Complexidades no pior caso (padrão)
Algoritmo
Pior caso
Merge sort
O(n log n)
Quick sort
O(n²)
Bubble sort
O(n²)
Insertion sort
O(n²)
Selection sort
O(n²)
1Merge sortO(n log n)
2Quick sortO(n²)
3Bubble sortO(n²)
4Insertion sortO(n²)
5Selection sortO(n²)
LEVEL · soulevel.com.br
Análise das alternativas
Alternativa A — ❌ Incorreta
Quick sort: no pior caso, quando o pivô é sempre o menor ou maior elemento (ex.: vetor já ordenado e pivô fixo), a complexidade é O(n²). Muitos candidatos confundem com a complexidade média, que é O(n log n).
Alternativa B — ✅ Correta ⟵ GABARITO
Merge sort: utiliza divisão e conquista, sempre dividindo o vetor ao meio e intercalando. No pior caso, executa O(n log n) comparações, independentemente da entrada.
Alternativa C — ❌ Incorreta
Bubble sort: percorre o vetor repetidamente trocando elementos adjacentes, realizando O(n²) comparações no pior caso (vetor inversamente ordenado).
Alternativa D — ❌ Incorreta
Insertion sort: insere cada elemento na posição correta deslocando os demais; pior caso O(n²) (vetor decrescente).
Alternativa E — ❌ Incorreta
Selection sort: seleciona o menor elemento a cada iteração; pior caso O(n²), independentemente da ordenação inicial.