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
- Escreva um algoritmo em linguagem descritiva que, recebendo uma lista de arestas (edge list) de um grafo com V vértices…
- Ao decompor um algoritmo complexo, que documentação técnica mínima deve acompanhar cada função para permitir integração…
- Qual vantagem direta de transformar uma variável global em parâmetro de função ao decompor um algoritmo que manipula…
- Projete a decomposição de alto nível de um algoritmo que gera relatórios mensais de presença por aluno a partir de dados…
- Quais são, em ordem, as três etapas essenciais ao decompor um algoritmo complexo para facilitar sua resolução?
- Ao decompor um algoritmo que calcula estatísticas de temperatura, qual subtarefa trata de identificar e excluir outliers…
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