A Ordenação por Inserção (Insertion Sort) é um algoritmo eficiente para ordenar um número
pequeno de elementos (Cormen et al., 2024). Em cada passo, a partir de i = 2, o i-ésimo
elemento da sequência é transferido para o seu lugar apropriado no arranjo (vetor).
Sobre o método de ordenação por inserção, assinale a alternativa INCORRETA:

Question

A Ordenação por Inserção (Insertion Sort) é um algoritmo eficiente para ordenar um número
pequeno de elementos (Cormen et al., 2024). Em cada passo, a partir de i = 2, o i-ésimo
elemento da sequência é transferido para o seu lugar apropriado no arranjo (vetor).
Sobre o método de ordenação por inserção, assinale a alternativa INCORRETA: Alternativa A: O método possui complexidade de tempo O(n2
) no pior caso. Ou Alternativa B: O método ordena os elementos no arranjo original (in loco). Ou Alternativa C: O método é considerado estável, isto é, não altera a ordem de chaves idênticas. Ou Alternativa D: O método executa quantidades de passos iguais para ordenar duas sequências de entrada
de mesmo tamanho.

Qconcursos · Accepted Answer

Alternativa [D] O método executa quantidades de passos iguais para ordenar duas sequências de entrada
de mesmo tamanho. Gabarito: DFundamento decisivo: A comparação decisiva é entre entradas de mesmo tamanho, mas com ordem inicial diferente: no Insertion Sort, isso altera a quantidade de passos.Tema central: Propriedades do Insertion SortAnálise das alternativasAErradaNão pode ser a incorreta porque essa propriedade está correta: no pior caso, o Insertion Sort tem complexidade de tempo O(n^2).BErradaNão pode ser a incorreta porque essa descrição corresponde ao algoritmo: ele ordena no próprio arranjo, com uso de espaço extra constante, caracterizando ordenação in loco.CErradaNão pode ser a incorreta porque, na forma clássica do algoritmo, o Insertion Sort é estável: elementos com chaves iguais mantêm sua ordem relativa.DCertaA alternativa D é a incorreta porque o Insertion Sort não executa sempre a mesma quantidade de passos para sequências de mesmo tamanho. A quantidade de comparações e deslocamentos varia conforme a disposição inicial da entrada, como mostra a diferença entre vetor já ordenado e vetor em ordem inversa.Pegadinha da questãoA confusão explorada foi tratar “mesmo tamanho da entrada” como se implicasse “mesma quantidade de passos”, além de tomar o O(n^2) do pior caso como se fosse custo fixo para toda entrada de tamanho n.Dica para questões semelhantesQuando a alternativa falar em número de passos, verifique se o algoritmo depende apenas do tamanho da entrada ou também da disposição inicial dos elementos.Não transforme complexidade de pior caso em comportamento obrigatório para todas as entradas.Em questões com pedido de alternativa incorreta, primeiro separe as propriedades clássicas seguras do algoritmo e depois teste a afirmação que generaliza demais seu custo.

🎯 Saiba o que estudar

🎯 Saiba o que estudar

A Ordenação por Inserção (Insertion Sort) é um algoritmo efi...

Gabarito comentado

Gabarito: D

Clique para visualizar este gabarito

Questões de assuntos semelhantes

Provas relacionadas