Uma equipe de uma biblioteca digital precisa ordenar 50 mil registros pelo título das obras. A lista já está…
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 uma biblioteca digital precisa ordenar 50 mil registros pelo título das obras. A lista já está quase ordenada: em geral, cada registro está a poucas posições de sua posição final. Além disso, os registros que possuem títulos iguais devem manter a ordem original de cadastro, e o programa dispõe de pouca memória adicional. A equipe deseja escolher, inicialmente, um algoritmo adequado a essas condições. Com base nas características da lista e nas restrições de memória e estabilidade apresentadas, qual algoritmo de ordenação deve ser escolhido inicialmente?
- A) Seleção
- B) Bolha
- C) Rápida
- D) Combinação
- E) Inserção
✅ Resposta correta: alternativa E
Resolução passo a passo
- Identifique as exigências da questão. A lista está quase ordenada, com cada registro a poucas posições da posição final. Os títulos iguais devem manter a ordem original (estabilidade). A memória adicional é pouca (o algoritmo deve ser in-place, ou seja, usar memória extra constante).
- Analise o comportamento do Inserção nessas condições. O algoritmo percorre a lista e insere cada elemento na posição correta dentro do trecho já ordenado à esquerda. Quando a lista está quase ordenada, cada elemento precisa de poucas trocas ou deslocamentos, e o custo fica próximo de O(n + d), em que d é o número de inversões. Ele é estável, pois só desloca elementos maiores estritamente, sem ultrapassar elementos iguais, e usa memória extra constante.
- Verifique as demais opções. A Seleção não é estável e faz sempre cerca de n^2/2 comparações, sem aproveitar a quase ordenação. A Bolha é estável e in-place, mas, mesmo com otimização, faz muitas trocas entre elementos distantes e não é a escolha mais eficiente. A Rápida não é estável e tem pior caso O(n^2), que pode ocorrer em listas quase ordenadas dependendo do pivô. A Combinação é estável e tem desempenho garantido, mas exige memória auxiliar proporcional a n, o que contraria a restrição de pouca memória.
- Conclusão. Com base nas características da lista, na necessidade de estabilidade e na restrição de memória, o algoritmo adequado para a escolha inicial é a Inserção, que corresponde à alternativa E, em concordância com o gabarito oficial.
💡 Dica: Relacione estabilidade, pouca memória e eficiência em listas quase ordenadas.
Alternativa por alternativa
O aluno pode supor que a Seleção, por fazer poucas trocas (no máximo n-1), seja adequada para listas quase ordenadas. Ele ignora que ela continua fazendo cerca de n^2/2 comparações e não é estável.
O aluno pode considerar a Bolha adequada por ser estável e in-place, sem perceber que, mesmo com a otimização de parada antecipada, ela realiza muitas trocas de elementos que precisam deslocar-se várias posições, sendo menos eficiente que a Inserção nesse cenário.
Por que engana: Escolher um algoritmo conhecido por ser geralmente rápido, como o quicksort, sem considerar que a lista quase ordenada, a estabilidade e a pouca memória favorecem a inserção.
O aluno pode escolher a Rápida por acreditar que o algoritmo mais rápido em média é sempre a melhor escolha. Ele não considera que a Rápida não é estável, o que viola a exigência de manter a ordem dos títulos iguais, e que seu pior caso é quadrático.
O aluno pode pensar que, por ter desempenho garantido O(n log n) e ser estável, a Combinação resolve o problema. Ele esquece que a Combinação exige memória auxiliar proporcional ao tamanho da lista, o que contraria a restrição de pouca memória adicional.
O algoritmo de inserção é adequado para listas quase ordenadas, pois aproveita a ordem já existente e realiza poucas movimentações quando o número de inversões é pequeno. Além disso, pode ser implementado de modo estável e usando memória adicional constante, preservando a ordem original de registros com chaves iguais.
Raio-X da questão
Algoritmo de ordenação por inserção
avaliacao
Características dos algoritmos de ordenação · Complexidade de tempo e espaço
Revise estabilidade, complexidade e uso de memória dos algoritmos de ordenação.
Escolher um algoritmo conhecido por ser geralmente rápido, como o quicksort, sem considerar que a lista quase ordenada, a estabilidade e a pouca memória favorecem a inserção.
ciencia_tecnologia
tomada_decisao
cientifico
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 pesquisa precisa ordenar listas grandes de números coletados em diferentes regiões do Brasil. Para…
- 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…
- Uma biblioteca pública mantém um cadastro digital com 4.096 nomes de usuários, organizados em ordem alfabética. O…
- Ao criar um algoritmo para organizar uma biblioteca, você precisa garantir que os livros sejam armazenados em ordem…
🔎 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