Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — IF-MG 2024

Algoritmos e Estrutura de DadosAlgoritmos
Código
qg240041
Banca
IF-MG
Órgão
IF-MG
Ano
2024
Nível
Superior
Cargo
PROFESSOR EBTT - Ciência da Computação e Sistemas de Informação. - Ribeirão das Neves
Considere um arranjo (vetor) de inteiros com n elementos que está quase ordenado (isto é, apenas alguns elementos estão fora de ordem). Sabendo disso, você deseja escolher o algoritmo de ordenação que seja mais eficiente neste cenário. Qual das seguintes alternativas apresenta o melhor algoritmo de ordenação a ser escolhido para ordenar um arranjo (vetor) quase ordenado, em termos de desempenho esperado?
  1. AUtilizar o Quick Sort, pois, em média, tem complexidade O(n lg n). e funciona bem em dados quase ordenados, minimizando as trocas.
  2. BUtilizar o Heap Sort, pois garante complexidade O(n lg n). no pior caso e reorganiza eficientemente os elementos fora de ordem.
  3. CUtilizar o Insertion Sort, pois tem complexidade O(n) em um arranjo (vetor) quase ordenado e é eficiente em dados com pequenas desordens.
  4. DUtilizar o Merge Sort, pois é um algoritmo estável com complexidade O(n lg n) no pior caso e faz a ordenação em dois subarranjos (subvetor) para garantir uma ordenação eficiente.
  5. EUtilizar o Selection Sort, pois, apesar de sua complexidade O(n²), ele realiza o menor número de trocas possível, o que é ideal para arranjos (vetores) quase ordenados.
Revelar gabarito e comentário

GabaritoC — Utilizar o Insertion Sort, pois tem complexidade O(n) em um arranjo (vetor) quase ordenado e é eficiente em dados com pequenas desordens.

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 para dados quase ordenados

Gabarito: letra C. O Insertion Sort é o mais eficiente para arranjos quase ordenados, pois sua complexidade é O(n) nesse cenário (adaptativo). Ele percorre o vetor e insere cada elemento na posição correta, realizando poucas trocas, enquanto outros algoritmos como Quicksort podem degenerar para O(n²) e Heapsort ou Merge Sort não se beneficiam da ordenação parcial.

A tabela a seguir resume as complexidades típicas para o caso de dados quase ordenados:

Algoritmo

Melhor caso (quase ordenado)

Pior caso

Estável?

Insertion Sort

O(n)

O(n²)

Sim

Selection Sort

O(n²)

O(n²)

Não

Bubble Sort

O(n) (com otimização)

O(n²)

Sim

Quicksort

O(n log n) (médio), O(n²) (pior com pivô fixo)

O(n²)

Não

Heapsort

O(n log n)

O(n log n)

Não

Merge Sort

O(n log n)

O(n log n)

Sim

Algoritmos de ordenação
  • 1Adaptativos (quase ordenados)
    • Insertion Sort (O(n))
    • Bubble Sort (O(n) c/ otimização)
  • 2Não adaptativos
    • Quicksort (O(n²) pior caso)
    • Heapsort (O(n log n) fixo)
    • Merge Sort (O(n log n) fixo)
    • Selection Sort (O(n²) fixo)
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Afirma que o Quicksort minimiza trocas em dados quase ordenados. Na verdade, se o pivô for escolhido como o primeiro ou último elemento (prática comum), o Quicksort tende ao pior caso O(n²) em arrays quase ordenados, pois o particionamento fica desbalanceado. Não é a melhor escolha.

Alternativa B — ❌ Incorreta

O Heapsort garante O(n log n) no pior caso, mas não é adaptativo: executa o mesmo número de operações independentemente da ordenação inicial. Para dados quase ordenados, o Insertion Sort é mais rápido por ser O(n).

Alternativa C — ✅ Correta ⟵ GABARITO

Insertion Sort tem complexidade linear O(n) em arranjos quase ordenados, pois o laço interno é executado poucas vezes. É o algoritmo mais eficiente para esse cenário, sendo amplamente utilizado quando se sabe que os dados estão quase ordenados.

Alternativa D — ❌ Incorreta

Merge Sort tem complexidade O(n log n) no pior caso, mas não é adaptativo: sempre realiza O(n log n) operações e requer O(n) de memória extra. Não é tão eficiente quanto Insertion Sort para dados quase ordenados.

Alternativa E — ❌ Incorreta

Selection Sort tem complexidade O(n²) independentemente da ordenação, realizando muitas comparações (n²/2) mesmo com poucas trocas. Não é eficiente para dados quase ordenados.

Gabarito: letra C.

Link permanente: /questoes/qg240041