GabaritoE — Errado
Gabarito: E (Errado). A afirmação de que o Selection sort requer apenas O(1) de espaço de memória adicional é considerada Errada pelo CESPE, conforme o gabarito oficial. No entanto, cabe uma observação importante.
A maioria das referências em ciência da computação classifica o Selection sort como um algoritmo in-place, ou seja, ele reorganiza os elementos dentro do próprio array de entrada, utilizando apenas algumas variáveis auxiliares (como índices e uma variável temporária para a troca). Dessa forma, a complexidade de espaço adicional (além do array original) é realmente O(1) — constante e independente do tamanho da entrada.
A banca, porém, pode ter considerado que o algoritmo não é estritamente in-place, ou que há necessidade de espaço extra para a cópia dos elementos ordenados (caso seja usada uma implementação com um array auxiliar). Como a questão não especifica a implementação, a interpretação mais comum é de que o enunciado está correto, mas o gabarito oficial aponta o contrário.
Esta é uma questão na qual o entendimento técnico diverge do gabarito oficial. Em provas do CESPE, recomenda-se seguir a posição da banca. Para fins de estudo, lembre-se de que a implementação clássica e eficiente do Selection sort utiliza espaço auxiliar O(1).
Apesar da controvérsia, a resposta conforme o gabarito é E (Errado).
Link permanente: /questoes/ce141806