Para ordenar grandes conjuntos de dados em memória usando a estratégia dividir e conquistar e mantendo a…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções de problemas usando a técnica de decomposição e automatizar tais soluções usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para ordenar grandes conjuntos de dados em memória usando a estratégia dividir e conquistar e mantendo a estabilidade entre elementos iguais, qual algoritmo é mais indicado?
- A) Quick Sort
- B) Insertion Sort
- C) Merge Sort.
- D) Selection Sort
- E) Bubble Sort
✅ Resposta correta: alternativa C
Resolução passo a passo
- A questão pede um algoritmo de ordenação que use a estratégia dividir e conquistar, que seja adequado a grandes conjuntos de dados em memória e que preserve a estabilidade (elementos iguais mantêm sua ordem relativa original).
- Analisando os critérios, o Merge Sort divide o vetor em metades recursivamente, ordena cada metade e depois as intercala. Sua complexidade é O(n log n) no pior caso, o que o torna eficiente para grandes volumes, e a etapa de intercalação pode ser feita de forma estável, copiando primeiro o elemento da metade esquerda quando houver empate. Logo, atende a todos os requisitos.
- O Quick Sort também usa dividir e conquistar e é muito rápido na prática, mas não é estável em sua implementação usual e tem pior caso O(n^2).
- O Insertion Sort, o Selection Sort e o Bubble Sort são algoritmos quadráticos, não usam dividir e conquistar e são ineficientes para grandes conjuntos; o Insertion Sort e o Bubble Sort são estáveis, mas não atendem ao critério de eficiência para grandes dados, e o Selection Sort nem sempre é estável.
- Portanto, a alternativa correta é a C (Merge Sort), em concordância com o gabarito oficial.
💡 Dica: Considere os algoritmos de ordenação estáveis.
Alternativa por alternativa
O aluno associa dividir e conquistar e alta velocidade ao Quick Sort, sem considerar que a estabilidade é exigida explicitamente no enunciado e que essa implementação não a garante.
Por que engana: Confundir a estabilidade dos algoritmos, escolhendo um que não mantém a ordem relativa de elementos iguais.
O aluno lembra que o Insertion Sort é estável e pensa que isso basta, ignorando que ele não usa dividir e conquistar e tem desempenho quadrático, inadequado para grandes conjuntos.
Merge Sort aplica dividir e conquistar, é estável por preservar ordem de iguais ao mesclar e tem complexidade O(n log n) consistente para grandes volumes.
O aluno confunde a simplicidade de implementação do Selection Sort com adequação a grandes dados, sem perceber que ele não usa dividir e conquistar e não garante estabilidade.
O aluno considera o Bubble Sort um método de ordenação 'clássico' e suficiente, sem notar que ele é quadrático, não segue a estratégia dividir e conquistar e só serve para conjuntos pequenos.
Raio-X da questão
algoritmos de ordenação
avaliacao
algoritmos de ordenação · estratégia dividir e conquistar
Revisar os algoritmos de ordenação estáveis e suas características.
Confundir a estabilidade dos algoritmos, escolhendo um que não mantém a ordem relativa de elementos iguais.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Uma plataforma de serviços públicos precisa organizar, em ordem crescente de protocolo, uma lista de registros que pode…
- Uma equipe de uma biblioteca digital precisa ordenar 50 mil registros pelo título das obras. A lista já está quase…
- Uma equipe de pesquisa precisa ordenar listas grandes de números coletados em diferentes regiões do Brasil. Para…
- Em uma atividade, os alunos precisam ordenar uma lista grande de números. O professor explicou que, para esse caso, a…
- Em um concurso de programação, os participantes devem criar um algoritmo que organize uma lista de dados. Qual abordagem…
- Em uma competição de programação, uma equipe precisa ordenar uma lista muito grande de notas. Todas as notas são números…
Todas as questões de Estratégias de solução de problemas - Decomposição
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog