Questão de Algoritmos e Estrutura de Dados — Algoritmos — Instituto Ágata 2025
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg571589
Banca
Instituto Ágata
Órgão
Prefeitura de Piçarra - PA
Ano
2025
Nível
Superior
Cargo
Professor de Informática
Um professor está precisando ordenar os seus alunos pelas notas obtidas na última avaliação. Considerando que são muitos alunos distribuídos aleatoriamente e que a menor nota foi zero e a maior foi dez, qual o algoritmo de ordenação apropriado que o professor deve utilizar para essa tarefa?
ABubble sort
BMerge sort
CInsertion sort
DCount sort
Revelar gabarito e comentário▾
GabaritoD — Count sort
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Algoritmos de ordenação – Count sort
Gabarito: letra D. A questão descreve um cenário com muitos alunos e notas que variam apenas de 0 a 10, uma faixa pequena e conhecida. Nesse contexto, o algoritmo de ordenação por contagem (counting sort) é o mais adequado, pois sua complexidade é linear O(n + k), sendo k o tamanho do intervalo de valores (aqui, k = 11). Os demais algoritmos (bubble, merge, insertion) são baseados em comparação e não exploram essa característica dos dados, apresentando pior desempenho assintótico.
A ordenação por contagem (Count sort) é um algoritmo não baseado em comparação, que utiliza a contagem de frequências para posicionar os elementos diretamente. Quando o intervalo de valores possíveis (k) é pequeno em relação ao número de elementos (n), o algoritmo é extremamente eficiente, rodando em tempo O(n + k). No caso das notas de 0 a 10, k = 11, o que torna o Count sort a escolha ótima.
1Criar vetor de contagem (k=11)
2Contar frequência de cada nota
3Acumular contagens (posições)
4Posicionar alunos ordenados
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Bubble sort é um algoritmo de ordenação por comparação com complexidade O(n²) no pior e no melhor caso. Embora funcione para qualquer conjunto, não aproveita a faixa limitada das notas, sendo ineficiente para muitos alunos.
Alternativa B — ❌ Incorreta
Merge sort é um algoritmo de ordenação por comparação com complexidade O(n log n) no pior caso. Embora seja eficiente para grandes volumes, ainda é baseado em comparações e não tira proveito do fato de as notas serem inteiros em um intervalo pequeno. O Count sort o supera em velocidade quando k é pequeno.
Alternativa C — ❌ Incorreta
Insertion sort é um algoritmo de ordenação por comparação com complexidade O(n²) no pior caso. Semelhante ao bubble sort, não é adequado para grandes conjuntos, especialmente quando a faixa de valores é restrita e conhecida.
Alternativa D — ✅ Correta ⟵ GABARITO
Count sort é o algoritmo ideal, pois utiliza as próprias chaves (notas de 0 a 10) como índices para ordenar os elementos em tempo linear O(n + k). Como k = 11 é pequeno e fixo, o algoritmo é extremamente rápido, independentemente do tamanho da entrada.