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
- Durante uma campanha de arrecadação, uma escola receberá alimentos e produtos de higiene para montar cestas destinadas a…
- Em um exercício de preparação para períodos de chuva intensa, uma central municipal de Defesa Civil precisa localizar…
- Em ações de fiscalização ambiental no Brasil, imagens de satélite podem ser comparadas em diferentes datas para indicar…
- Uma família criou um programa para organizar as compras do mês. O programa recebe os preços, soma os produtos e…
- — Sem conexão estável no rio, o alerta precisa aparecer no próprio tablet — afirmou a técnica que acompanha sons de aves…
- Falhas em formulários digitais de serviços públicos levaram um setor de tecnologia a testar cinco programas de análise…
🔎 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