Algoritmos e Estrutura de Dados · IF-MG · 2024 | Questão sqc-qg240042

Algoritmos e Estrutura de DadosAlgoritmos

Código: qg240042
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

Os algoritmos QuickSort e MergeSort são conhecidos algoritmos de ordenação e que apresentam um bom desempenho. Em relação as diferenças entre os dois algoritmos é correto afirmar:

AO algoritmo QuickSort apresenta complexidade de tempo de O(n lg n). no pior caso, enquanto o algoritmo MergeSort apresenta complexidade de tempo de O(n²).
BO algoritmo QuickSort utiliza uma estratégia de particionar o arranjo (vetor) a ser ordenado utilizando uma função chamada partition que divide todo arranjo (vetor) e depois junta as partes divididas de forma ordenada. Enquanto o algoritmo MergeSort utiliza uma estratégia criando um pivot que separa o arranjo (vetor) em partes menores que o pivot a esquerda e maiores que o pivot a direita.
CO algoritmo QuickSort apresenta complexidade de tempo de O(n²) no pior caso, enquanto o algoritmo MergeSort apresenta complexidade de tempo de O(n lg n).
DO algoritmo MergeSort utiliza uma estratégia de particionar o arranjo (vetor) a ser ordenado utilizando uma função chamada partition que divide todo arranjo (vetor) e depois junta as partes divididas de forma ordenada. Enquanto o algoritmo QuickSort utiliza uma estratégia criando um pivot que separa o arranjo (vetor) em partes menores que o pivot a esquerda e maiores que o pivot a direita.
EOs algoritmos QuickSort e MergeSort divergem somente sobre o seu paradigma de programação em que o primeiro utiliza um paradigma de programação dinâmica e o segundo um paradigma de divisão e conquista.

Revelar gabarito e comentário

GabaritoB — O algoritmo QuickSort utiliza uma estratégia de particionar o arranjo (vetor) a ser ordenado utilizando uma função chamada partition que divide todo arranjo (vetor) e depois junta as partes divididas de forma ordenada. Enquanto o algoritmo MergeSort utiliza uma estratégia criando um pivot que separa o arranjo (vetor) em partes menores que o pivot a esquerda e maiores que o pivot a direita.

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”.

QuickSort e MergeSort

Gabarito oficial: letra B. A banca considerou correta a afirmação de que o QuickSort particiona o vetor com a função partition e depois junta as partes ordenadas, enquanto o MergeSort cria um pivot que separa o vetor em partes menores à esquerda e maiores à direita. Embora essa descrição esteja invertida em relação ao que a literatura clássica ensina (o QuickSort é que usa pivot e o MergeSort é que divide e intercala), a questão foi elaborada com essa redação. Portanto, segundo o gabarito, a alternativa B é a resposta.

NÃO CAIA NESSA!

A banca inverteu as definições das duas estratégias: o QuickSort realmente utiliza um pivot e a função partition, e o MergeSort divide o vetor em duas metades e depois as intercala (junta de forma ordenada). A alternativa B troca essas características, mas foi considerada certa pela banca. Fique atento: em provas de outras bancas, a descrição correta é a da letra D.

Alternativa A — ❌ Incorreta

Afirma que QuickSort tem pior caso O(n log n) e MergeSort O(n²). Na verdade, QuickSort tem pior caso O(n²) e MergeSort O(n log n) em todos os casos.

Alternativa B — ✅ Correta ⟵ GABARITO

Conforme o gabarito oficial, esta é a resposta correta, apesar da inversão conceitual descrita acima.

Alternativa C — ❌ Incorreta (segundo gabarito)

Afirma que QuickSort tem pior caso O(n²) e MergeSort O(n log n) — o que é tecnicamente correto. Porém, para a banca essa não foi a alternativa escolhida.

Alternativa D — ❌ Incorreta (segundo gabarito)

Descreve corretamente MergeSort (partition e intercalação) e QuickSort (pivot), mas não foi a opção do gabarito.

Alternativa E — ❌ Incorreta

Afirma que QuickSort usa programação dinâmica e MergeSort divisão e conquista. Ambos são algoritmos de divisão e conquista; programação dinâmica não se aplica.

Conclusão: Resposta oficial é letra B, mas é essencial conhecer a versão correta (letra D) para outras provas.

Link permanente: /questoes/qg240042