Em algoritmos de ordenação, o termo 'estabilidade' refere-se ao comportamento diante de elementos com chaves…

Questão

Em algoritmos de ordenação, o termo 'estabilidade' refere-se ao comportamento diante de elementos com chaves iguais. O que significa que um algoritmo seja estável?

1. A) Preservar a ordem relativa dos elementos que têm chaves iguais.
2. B) Um algoritmo deve sempre retornar os elementos em ordem decrescente.
3. C) Um algoritmo é estável se não utiliza comparação entre elementos.
4. D) Um algoritmo estável pode misturar a ordem de elementos iguais.
5. E) A estabilidade implica que elementos com chaves diferentes fiquem em primeiro lugar.

✅ Resposta correta: alternativa A

Resolução passo a passo

1. Em ordenação, a estabilidade diz respeito ao que acontece com elementos que têm chaves iguais. Um algoritmo é estável quando, após a ordenação, dois elementos com a mesma chave aparecem na mesma ordem relativa em que estavam na entrada.
2. Exemplo: se a lista tem (Ana, 3) e depois (Bruno, 3), um algoritmo estável sempre deixará Ana antes de Bruno na saída, pois ambos têm chave 3 e a ordem original foi preservada.
3. Portanto, a alternativa A está correta, pois define exatamente a preservação da ordem relativa entre chaves iguais.
4. Por que as outras estão erradas:
5. B) Ordem decrescente não é exigência de estabilidade; a ordem pode ser crescente ou decrescente, e isso não define estabilidade.
6. C) Não usar comparação não caracteriza estabilidade; algoritmos que comparam elementos podem ser estáveis (como o Merge Sort) e outros que não comparam, como o Counting Sort, podem ou não ser estáveis.
7. D) Um algoritmo estável justamente não mistura a ordem de elementos iguais; a alternativa inverte o conceito.
8. E) A estabilidade trata da relação entre elementos de mesma chave, e não de colocar chaves diferentes em primeiro lugar; a ordenação é que define a posição das chaves.
9. Conclusão: o gabarito A está correto.

💡 Dica: Defina o que caracteriza um algoritmo estável em ordenação.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Ao implementar num algoritmo a ordenação de uma matriz de registros 'tarefas' por campo 'prioridade', que propriedade do…
• Ao ordenar todos os registros de uma matriz por campo 'nome' e preservar a ordem relativa entre registros com o mesmo…
• Ao implementar um algoritmo de ordenação para uma matriz 'alunos' primeiro por 'nota' e em seguida por 'nome' sem perder…
• Uma plataforma de serviços públicos precisa organizar, em ordem crescente de protocolo, uma lista de registros que pode…
• Qual o objetivo de um algoritmo de ordenação?
• Para ordenar grandes conjuntos de dados em memória usando a estratégia dividir e conquistar e mantendo a estabilidade…

Todas as questões de Programação - Tipos de dados