GabaritoC — ordenação por inserção.
Gabarito: letra C. A ordenação por inserção (insertion sort) é um algoritmo que ordena elementos diretamente no próprio array, utilizando apenas uma quantidade constante de espaço adicional (O(1)), ou seja, algumas variáveis auxiliares para controle. O gabarito oficial aponta essa alternativa como correta.
A questão cobra o conhecimento de quais algoritmos são in-place (que não requerem memória extra proporcional ao tamanho da entrada). Dentre as opções, o merge sort (ordenção por mistura) é o único que claramente não é in-place, pois precisa de um array auxiliar de tamanho O(n) no processo de mesclagem. As demais alternativas – selection sort, bubble sort e heapsort – também podem ser implementadas com espaço O(1) adicional. Contudo, a banca definiu a ordenação por inserção como resposta oficial, provavelmente por ser um exemplo clássico e frequentemente cobrado em provas.
Algoritmo | Complexidade de espaço adicional |
|---|---|
A) Ordenação por seleção | O(1) (in-place) |
B) Ordenação por mistura (merge sort) | O(n) |
C) Ordenação por inserção | O(1) (in-place) |
D) Ordenação por flutuação (bubble sort) | O(1) (in-place) |
E) Ordenação heapsort | O(1) (in-place) |
A ordenação por seleção também é in-place e utiliza espaço O(1). Apesar disso, não é a resposta indicada pelo gabarito oficial. A banca pode ter considerado que o insertion sort é o mais representativo, ou simplesmente definiu C como gabarito.
A ordenação por mistura (merge sort) não é in-place: requer um array auxiliar de tamanho O(n) para realizar a mesclagem, violando a condição de O(1) adicional.
A ordenação por inserção é um algoritmo in-place: os elementos são inseridos na posição correta dentro do próprio array, utilizando apenas variáveis temporárias. Sua complexidade de espaço adicional é constante, O(1).
A ordenação por flutuação (bubble sort) também é in-place com O(1) de espaço extra. Não é a resposta do gabarito, embora tecnicamente atenda ao requisito.
O heapsort é in-place quando implementado iterativamente (ou com recursão de cauda otimizada), usando espaço adicional O(1). Novamente, não foi a escolha da banca.
Cuidado para não confundir o merge sort com os demais: ele é o único que não é in-place (requer O(n) de memória). As outras opções (seleção, inserção, flutuação, heapsort) são todas in-place, o que torna a questão ambígua. Na prova, memorize que a banca costuma cobrar o insertion sort como exemplo clássico de algoritmo com espaço O(1).
Gabarito: letra C — ordenação por inserção.
Link permanente: /questoes/ce134524