Em uma indústria de logística, um software recebe uma lista de códigos de itens e precisa ordená-los…
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
Em uma indústria de logística, um software recebe uma lista de códigos de itens e precisa ordená-los. Observando o passo a passo curto a seguir: 1) comparar itens adjacentes; 2) trocar se necessário; 3) repetir até não haver trocas. Qual afirmação descreve corretamente esse algoritmo?
- A) É ordenação por bolha, estável e in-place; pior/médio O(n^2); melhor caso O(n) com otimização de parada.
- B) É ordenação por bolha, in-place, mas não é estável; pior/médio O(n^2).
- C) É divisão e conquista; separa a lista em partes e depois junta os itens.
- D) É ordenação por bolha; pior caso O(n^2); tempo médio O(n log n).
- E) É uma ordenação que não troca itens adjacentes durante o processo.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Identifique o algoritmo descrito. Comparar itens adjacentes, trocar se necessário e repetir até não haver mais trocas é a descrição da ordenação por bolha (bubble sort).
- Analise a alternativa A. A ordenação por bolha é estável quando só troca dois itens vizinhos se o da esquerda for estritamente maior que o da direita, pois itens iguais não mudam de posição relativa. Ela é in-place, pois usa memória auxiliar constante. Seu pior e caso médio são O(n^2), e o melhor caso é O(n) quando há uma flag de parada que encerra a execução ao detectar uma passagem sem trocas. Logo, A descreve corretamente o algoritmo.
- A alternativa B está errada, pois a ordenação por bolha padrão é estável; a afirmação de que não é estável contradiz essa propriedade.
- A alternativa C está errada, pois divisão e conquista (como merge sort e quick sort) separa a lista em partes menores, o que não ocorre no procedimento descrito.
- A alternativa D está errada, pois o tempo médio da ordenação por bolha é O(n^2), e não O(n log n), que é a complexidade média de algoritmos como merge sort e quick sort.
- A alternativa E está errada, pois o próprio passo 2 do enunciado é a troca de itens adjacentes, justamente o mecanismo que o algoritmo usa.
- Conclusão: a alternativa correta é a A, em concordância com o gabarito oficial.
💡 Dica: Identifique a ordenação pelas trocas entre elementos adjacentes e avalie suas propriedades e complexidades.
Alternativa por alternativa
O algoritmo compara itens vizinhos e os troca quando necessário. Com a otimização de parada, se não houver trocas, ele termina em O(n).
Acredita que trocar elementos de posição quebra a ordem relativa entre itens iguais, confundindo estabilidade com a ausência de memória extra (in-place).
Confunde a ordenação por bolha com algoritmos de divisão e conquista como merge sort ou quick sort, que de fato dividem a lista em partes.
Transfere para a ordenação por bolha a complexidade média O(n log n) de algoritmos mais eficientes, sem verificar a análise do método descrito.
Por que engana: Confundir a complexidade média da ordenação por bolha com O(n log n) ou afirmar que ela não é estável, ignorando o funcionamento das trocas adjacentes.
Não percebe que o passo 2 do enunciado já envolve a troca de itens adjacentes, lendo de forma incorreta a descrição do algoritmo.
Raio-X da questão
Algoritmo de ordenação por bolha
avaliacao
Comparação e troca de elementos · Notação de complexidade assintótica
Revise estabilidade, uso de memória e complexidade nos casos melhor, médio e pior do bubble sort.
Confundir a complexidade média da ordenação por bolha com O(n log n) ou afirmar que ela não é estável, ignorando o funcionamento das trocas adjacentes.
ciencia_tecnologia
tomada_decisao
cotidiano
Questões parecidas com resolução
- Em um projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
- Uma biblioteca escolar recebeu caixas de livros doados para uma feira de troca. Para registrar os exemplares, a equipe…
- Um centro cultural público oferece inscrições on-line para atividades com critérios variados. Na oficina de teatro…
- Uma escola está testando dois protótipos de aplicativo para que estudantes consultem mudanças de sala, horários e…
- Uma secretaria municipal de educação está digitalizando pedidos de transporte escolar e de atendimento em contraturno…
- — O cartaz não pode sair duas vezes, pois a feira começa em uma hora — alertou a coordenadora do centro cultural. No…
🔎 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