Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — IF-PI 2026

Algoritmos e Estrutura de DadosAlgoritmos
Código
qg709988
Banca
IF-PI
Órgão
IF-PI
Ano
2026
Nível
Superior
Cargo
Professor EBTT - Informática
Considere os algoritmos clássicos de ordenação: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort e Quick Sort.Analise as afirmativas a seguir com base em suas propriedades formais de complexidade, estabilidade e uso de memória na implementação tradicional apresentada na literatura clássica.I. O Insertion Sort possui complexidade de tempo O(n²) no pior caso e pode apresentar complexidade O(n) no melhor caso, quando o vetor já se encontra ordenado.II. O Merge Sort apresenta complexidade O(n log n) nos casos melhor, médio e pior, é estável e, em sua implementação tradicional, requer espaço adicional proporcional a O(n).III. O Quick Sort apresenta complexidade média O(n log n) e pior caso O(n²), podendo este ocorrer quando o pivô escolhido produz partições altamente desbalanceadas.IV. O Selection Sort possui complexidade O(n²) nos casos melhor, médio e pior e, em sua implementação tradicional, não é considerado um algoritmo estável.Assinale a alternativa CORRETA:
  1. AApenas I, II e III estão corretas.
  2. BApenas I, II e IV estão corretas.
  3. CApenas II e III estão corretas.
  4. DTodas as alternativas estão corretas.
  5. EApenas III e IV estão corretas.
Revelar gabarito e comentário

GabaritoD — Todas as alternativas estão corretas.

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 Clássicos

Gabarito: letra D (Todas as afirmativas estão corretas). As quatro afirmativas descrevem corretamente as propriedades conhecidas dos algoritmos Insertion Sort, Merge Sort, Quick Sort e Selection Sort, de acordo com a literatura clássica de algoritmos (Cormen et al., 2009).

A banca testa o conhecimento de complexidade de tempo (melhor, médio e pior caso), estabilidade e uso de memória adicional. Abaixo, uma tabela comparativa resume as principais características:

Algoritmo

Melhor Caso

Caso Médio

Pior Caso

Estável?

Espaço Extra

Insertion Sort

O(n)

O(n²)

O(n²)

Sim

O(1)

Merge Sort

O(n log n)

O(n log n)

O(n log n)

Sim

O(n)

Quick Sort

O(n log n)

O(n log n)

O(n²)

Não*

O(log n)

Selection Sort

O(n²)

O(n²)

O(n²)

Não**

O(1)

*Quick Sort é instável na implementação tradicional; pode ser estabilizado com custo adicional. **Selection Sort é instável, pois troca elementos distantes, podendo desfazer ordem relativa.

Afirmativa I — ✅ Correta

Insertion Sort: realmente, no melhor caso (vetor já ordenado), o algoritmo realiza apenas uma comparação por elemento, resultando em O(n). No pior caso (vetor inversamente ordenado), o número de comparações é quadrático, O(n²).

Afirmativa II — ✅ Correta

Merge Sort: é um algoritmo de divisão e conquista que sempre divide o vetor ao meio, garantindo O(n log n) em todos os casos. É estável (a ordem de elementos iguais é preservada) e, por usar vetores auxiliares durante a intercalação, requer espaço extra O(n).

Afirmativa III — ✅ Correta

Quick Sort: apresenta complexidade média O(n log n) devido à boa escolha do pivô. No pior caso, quando as partições são muito desbalanceadas (por exemplo, quando o pivô é sempre o menor ou o maior elemento), o número de comparações atinge O(n²).

Afirmativa IV — ✅ Correta

Selection Sort: realiza sempre (n-1) + (n-2) + ... + 1 = O(n²) comparações, independentemente da ordenação inicial. Na implementação tradicional (sem estabilidade forçada), ele não é estável, pois troca o elemento selecionado diretamente com o primeiro da parte não ordenada, podendo inverter a ordem de elementos iguais.

PEGA ESSA DICA!

Para memorizar, associe cada algoritmo a seu ponto forte: Insertion Sort é rápido em dados quase ordenados; Merge Sort é estável e previsível; Quick Sort é rápido na média, mas cuidado com pivô ruim; Selection Sort é simples, mas sempre quadrático e instável.

Conclusão: Todas as afirmativas (I, II, III e IV) estão corretas. Portanto, o gabarito é a letra D.

Link permanente: /questoes/qg709988