Em uma competição de programação, uma equipe precisa ordenar uma lista muito grande de notas. Todas as notas…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Utilizar algoritmos clássicos de manipulação sobre listas.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em uma competição de programação, uma equipe precisa ordenar uma lista muito grande de notas. Todas as notas são números inteiros de 0 a 10, e o principal objetivo é gastar o menor tempo possível na ordenação. Qual algoritmo é mais adequado para ordenar essa lista com eficiência, aproveitando que existem apenas 11 valores possíveis?
- A) Método da bolha (Bubble Sort)
- B) Ordenação por contagem (Counting Sort)
- C) Seleção simples (Selection Sort)
- D) QuickSort
- E) Inserção (Insertion Sort)
✅ Resposta correta: alternativa B
Resolução passo a passo
- Identifique o dado-chave do enunciado: a lista é muito grande, os valores são inteiros de 0 a 10 (apenas 11 valores possíveis) e o objetivo é ordenar no menor tempo possível.
- Lembre que algoritmos por comparação (Bubble, Selection, Insertion e QuickSort) não conseguem, no caso médio, ordenar menos do que n log n comparações, e os quadráticos (Bubble, Selection, Insertion) são lentos para listas grandes.
- Perceba que, quando o universo de valores é pequeno e conhecido, é possível contar quantas vezes cada valor aparece e reconstruir a lista na ordem, sem comparar elementos entre si.
- Esse método é a ordenação por contagem (Counting Sort). Ele percorre a lista uma vez para contar as ocorrências de cada um dos 11 valores e depois escreve cada valor na quantidade indicada, com complexidade proporcional a n + k, onde k = 11. Logo, é linear no tamanho da lista.
- Por que as outras estão erradas: A) o Bubble Sort é quadrático e ineficiente para listas grandes; C) o Selection Sort também é quadrático, fazendo sempre o mesmo número de comparações; D) o QuickSort é eficiente em geral, mas é baseado em comparações e não aproveita a faixa pequena de valores; E) o Insertion Sort é quadrático no caso médio e no pior caso, sendo lento para listas muito grandes.
- Conclusão: a alternativa B é a mais adequada, pois explora diretamente a existência de apenas 11 valores possíveis, em conformidade com o gabarito oficial.
💡 Dica: Considere diferentes algoritmos de ordenação e suas eficiências.
Alternativa por alternativa
Acredita que o Bubble Sort, por ser o mais conhecido e simples, é a melhor opção, ignorando que sua complexidade quadrática o torna lento para listas muito grandes.
Por que engana: Escolher o método da bolha por ser o mais simples, sem considerar sua ineficiência em listas grandes.
A ordenação por contagem registra quantas vezes cada nota aparece. Como os valores possíveis estão limitados de 0 a 10, o algoritmo percorre a lista e depois organiza os resultados em tempo proporcional ao tamanho da lista, sem precisar comparar cada nota com todas as outras. Por isso, é a opção mais adequada para esse caso.
Supõe que o Selection Sort, por fazer poucas trocas, seja eficiente, sem perceber que ele realiza sempre cerca de n^2/2 comparações.
Considera que o QuickSort é sempre o mais rápido possível e não percebe que, com poucos valores distintos, ele não aproveita essa informação e continua baseado em comparações.
Acha que o Insertion Sort é eficiente porque funciona bem em listas quase ordenadas, sem notar que o enunciado trata de uma lista muito grande e arbitrária, com custo quadrático.
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 complexidades.
Escolher o método da bolha por ser o mais simples, sem considerar sua ineficiência em listas grandes.
ciencia_tecnologia
pensamento_critico
cotidiano
Questões parecidas com resolução
- Em uma competição de programação, os alunos devem desenvolver um algoritmo que ordene uma lista de notas de teste. Qual…
- Em um concurso de programação, os participantes devem criar um algoritmo que organize uma lista de dados. Qual abordagem…
- Em uma escola pública, a equipe de tecnologia está desenvolvendo um sistema para gerar um relatório de notas. Antes de…
- Uma equipe de uma biblioteca digital precisa ordenar 50 mil registros pelo título das obras. A lista já está quase…
- Descreva um algoritmo que ordene uma lista de notas de alunos em ordem crescente. Quais passos são necessários para…
- Em uma competição de programação, os participantes precisam criar um algoritmo que ordene uma lista de números. Qual é 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