Algoritmos e Estrutura de Dados · INSTITUTO AOCP · 2022 | Questão sqc-qq762110

Algoritmos de ordenação: Merge sort e Quicksort

Gabarito: letra D. A estratégia comum a ambos os algoritmos é dividir e conquistar (divide and conquer): o problema original é dividido recursivamente em subproblemas menores (partes do vetor), cada subproblema é resolvido separadamente, e as soluções são combinadas para obter a solução final. Essa é a essência do paradigma, presente tanto no merge sort (divide o vetor ao meio, ordena cada metade e intercala) quanto no quicksort (escolhe um pivô, particiona e ordena recursivamente as partições).

A banca cobra o conhecimento do paradigma que une esses dois algoritmos clássicos. As demais alternativas se referem a conceitos relacionados, mas não à estratégia principal.

Estratégia	Merge Sort	Quicksort	Paradigma comum
Dividir e conquistar	Divide o vetor ao meio, ordena cada metade recursivamente e intercala	Escolhe um pivô, particiona o vetor e ordena recursivamente as partições	Sim
Definição de pivô	Não utiliza pivô	Utiliza pivô para particionar	Não
Combinação	Intercala as duas metades ordenadas	Não combina subvetores; apenas particiona	Não
Equação de recorrência	Ferramenta de análise de complexidade (ex.: T(n)=2T(n/2)+O(n))	Ferramenta de análise de complexidade	Não é estratégia de ordenação
Árvore binária balanceada	Estrutura de dados, não estratégia de ordenação	Estrutura de dados, não estratégia de ordenação	Não

Dividir e conquistar

1Merge sort
- Divide ao meio
- Ordena recursivamente
- Intercala (combina)
2Quicksort
- Escolhe pivô
- Particiona
- Ordena recursivamente

LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Equação de recorrência é uma ferramenta matemática usada para descrever o tempo de execução de algoritmos recursivos (ex.: $T(n)=2T(n/2)+O(n)$ para o merge sort), mas não é a estratégia de ordenação em si. Confunde-se o método de análise com o método de projeto do algoritmo.

Alternativa B — ❌ Incorreta

Definição de pivô é uma etapa específica do quicksort, usada na partição. O merge sort não utiliza pivô. Portanto, não pode ser a estratégia comum.

Alternativa C — ❌ Incorreta

Combinação (ou intercalação) é a etapa de merge do merge sort, mas o quicksort não combina subvetores — ele apenas particiona. A combinação é parte do merge sort, não o paradigma geral.

Alternativa D — ✅ Correta ⟵ GABARITO

Dividir e conquistar é exatamente a estratégia que ambos empregam. No merge sort: divide o vetor ao meio (divisão), ordena recursivamente cada metade (conquista), e intercala (combinação). No quicksort: escolhe um pivô e particiona (divisão), ordena recursivamente as partições (conquista). Apesar de detalhes diferentes, o paradigma é o mesmo.

Alternativa E — ❌ Incorreta

Árvore binária balanceada é uma estrutura de dados, não uma estratégia de ordenação. Embora o merge sort possa ser visualizado com uma árvore de recursão, o conceito central não é a árvore em si.

PEGA ESSA DICA!

Para memorizar, associe "divide and conquer" a algoritmos que quebram o problema em partes menores e depois juntam as soluções. Outros exemplos além do merge sort e quicksort são o algoritmo de busca binária e o algoritmo de ordenação por intercalação externa. Nas provas, sempre que a banca perguntar o paradigma comum entre dois algoritmos que "dividem" o problema, pense em dividir e conquistar.

Gabarito: letra D.