Uma plataforma de serviços públicos precisa organizar, em ordem crescente de protocolo, uma lista de registros…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar e construir a solução de problemas por meio de refinamentos, utilizando diversos níveis de abstração desde a especificação até a implementação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Uma plataforma de serviços públicos precisa organizar, em ordem crescente de protocolo, uma lista de registros que pode conter milhões de itens. Como a ordem relativa entre registros com o mesmo protocolo deve ser preservada, o algoritmo precisa ser estável. Além disso, a equipe exige que o tempo de execução permaneça limitado por uma função da ordem n log n, mesmo no pior caso. Há memória auxiliar disponível para a execução. Considerando simultaneamente a estabilidade exigida e a garantia de desempenho no pior caso descritas no texto, qual abordagem de ordenação atende melhor aos requisitos da plataforma?
- A) Ordenação por mesclagem
- B) Ordenação por seleção
- C) Ordenação por bolha
- D) Ordenação rápida
- E) Ordenação por inserção
✅ Resposta correta: alternativa A
Resolução passo a passo
- Os requisitos são dois: estabilidade (registros com o mesmo protocolo mantêm a ordem relativa) e tempo O(n log n) garantido no pior caso.
- Analisando as opções, a ordenação por mesclagem (merge sort) é estável, pois ao intercalar duas metades preserva a ordem original de elementos iguais, e tem complexidade O(n log n) no pior caso, pois divide a lista ao meio em cerca de log n níveis e processa n elementos por nível.
- A memória auxiliar disponível atende ao custo de espaço extra exigido pela mesclagem tradicional, que é O(n).
- A ordenação rápida (quicksort) não atende: sua complexidade no pior caso é O(n^2), e as implementações usuais não são estáveis.
- A ordenação por seleção também não atende: é O(n^2) em todos os casos e não é estável na implementação típica.
- A ordenação por bolha é estável, mas tem pior caso O(n^2), portanto não atende à exigência de desempenho.
- A ordenação por inserção é estável, mas seu pior caso também é O(n^2), o que a torna inadequada para listas de milhões de itens.
- Conclusão: apenas a ordenação por mesclagem atende simultaneamente à estabilidade e à garantia O(n log n) no pior caso, coincidindo com o gabarito oficial.
💡 Dica: Considere as diferentes técnicas de ordenação disponíveis.
Alternativa por alternativa
A ordenação por mesclagem é estável e apresenta complexidade de tempo O(n log n) no melhor, no médio e no pior caso. Como há memória auxiliar disponível, sua principal exigência adicional não impede seu uso. As demais abordagens apresentadas não atendem simultaneamente à estabilidade e à garantia de O(n log n) no pior caso.
O aluno pode ter associado a seleção à simplicidade e ao fato de fazer poucas trocas, sem verificar que ela é O(n^2) e não preserva a ordem relativa de elementos iguais.
Por que engana: Escolher uma abordagem menos eficiente, como a ordenação por bolha, que é mais simples, mas não ideal para listas grandes.
O aluno pode ter lembrado que a bolha é estável e ignorado o desempenho, esquecendo que seu pior caso é quadrático.
O aluno pode ter considerado a ordenação rápida como o algoritmo mais eficiente em geral, ignorando que seu pior caso é O(n^2) e que a implementação típica não é estável.
O aluno pode ter lembrado que a inserção é estável e eficiente em listas pequenas ou quase ordenadas, sem considerar que seu pior caso ainda é O(n^2) para milhões de itens.
Raio-X da questão
algoritmos de ordenação
avaliacao
algoritmos de ordenação · complexidade de algoritmos
Revisar os principais algoritmos de ordenação e suas eficiências.
Escolher uma abordagem menos eficiente, como a ordenação por bolha, que é mais simples, mas não ideal para listas grandes.
ciencia_tecnologia
pensamento_critico
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 equipe de pesquisa precisa ordenar listas grandes de números coletados em diferentes regiões do Brasil. Para…
- Para ordenar grandes conjuntos de dados em memória usando a estratégia dividir e conquistar e mantendo a estabilidade…
- Em uma atividade, os alunos precisam ordenar uma lista grande de números. O professor explicou que, para esse caso, a…
- Ao ordenar todos os registros de uma matriz por campo 'nome' e preservar a ordem relativa entre registros com o mesmo…
- Em uma competição de programação, uma equipe precisa ordenar uma lista muito grande de notas. Todas as notas são números…
🔎 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