Uma equipe de pesquisa precisa ordenar listas grandes de números coletados em diferentes regiões do Brasil…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Uma equipe de pesquisa precisa ordenar listas grandes de números coletados em diferentes regiões do Brasil. Para planejar o processamento, ela precisa saber que o tempo de ordenação não ficará quadrático mesmo no pior caso. Qual algoritmo atende a esse requisito, usando memória auxiliar?
- A) Bubble Sort
- B) Quick Sort
- C) Insertion Sort
- D) Merge Sort
- E) Selection Sort
✅ Resposta correta: alternativa D
Resolução passo a passo
- O requisito é um algoritmo de ordenação cujo tempo no pior caso não seja quadrático, ou seja, que seja O(n log n) ou melhor, e que use memória auxiliar, o que é uma característica do Merge Sort.
- O Merge Sort divide a lista ao meio recursivamente e depois intercala as metades já ordenadas. No pior caso, o tempo é O(n log n), pois há cerca de log n níveis de divisão e, em cada nível, o trabalho de intercalação é proporcional a n. A intercalação exige um vetor auxiliar, por isso ele atende também à menção à memória auxiliar.
- O Bubble Sort, o Insertion Sort e o Selection Sort têm complexidade de pior caso O(n^2), ou seja, quadrática, e por isso não atendem ao requisito.
- O Quick Sort tem caso médio O(n log n), mas no pior caso (por exemplo, com pivô mal escolhido em lista já ordenada) seu tempo é O(n^2), então não garante o requisito mesmo no pior caso.
- Portanto, a alternativa correta é a D, Merge Sort, que coincide com o gabarito oficial.
💡 Dica: Compare a complexidade de pior caso e o uso de memória auxiliar de cada algoritmo.
Alternativa por alternativa
Acredita que o Bubble Sort, por ser um algoritmo simples e famoso, tenha desempenho aceitável para listas grandes. Ignora que ele compara e troca pares repetidamente, o que é quadrático.
Associa o Quick Sort apenas ao caso médio O(n log n) e esquece que, no pior caso, com escolha ruim do pivô, o tempo vira O(n^2).
Por que engana: Escolher Quick Sort por sua eficiência média, sem considerar que seu pior caso pode ser quadrático.
Supõe que o Insertion Sort, por ser eficiente em listas pequenas ou quase ordenadas, seja bom para listas grandes no pior caso. Não percebe que o pior caso é O(n^2).
O Merge Sort tem tempo O(n log n) também no pior caso e usa memória auxiliar para combinar as partes ordenadas.
Pensa que, como o Selection Sort faz poucas trocas, seu tempo total é menor e não quadrático. Confunde número de trocas com número de comparações, que é sempre quadrático.
Raio-X da questão
Ordenação por intercalação
avaliacao
Complexidade de algoritmos · Algoritmos de ordenação
Revise a complexidade de pior caso dos algoritmos de ordenação e o uso de memória auxiliar.
Escolher Quick Sort por sua eficiência média, sem considerar que seu pior caso pode ser quadrático.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- Uma equipe de uma biblioteca digital precisa ordenar 50 mil registros pelo título das obras. A lista já está quase…
- Uma plataforma de serviços públicos precisa organizar, em ordem crescente de protocolo, uma lista de registros que pode…
- Em uma atividade, os alunos precisam ordenar uma lista grande de números. O professor explicou que, para esse caso, a…
- Em uma competição de programação, uma equipe precisa ordenar uma lista muito grande de notas. Todas as notas são números…
- Para ordenar grandes conjuntos de dados em memória usando a estratégia dividir e conquistar e mantendo a estabilidade…
- Em um concurso de programação, os participantes devem criar um algoritmo que organize uma lista de dados. Qual abordagem…
🔎 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