Questão de Algoritmos e Estrutura de Dados — Algoritmos — CESPE / CEBRASPE 2024

Insertion Sort: número máximo de movimentações

❌ ERRADO. O maior número de movimentações (deslocamentos/atribuições) no insertion sort ocorre no pior caso, que é quando o vetor está ordenado de forma decrescente, e não quando nenhum elemento é maior que seu sucessor (ou seja, ordenado de forma crescente). No melhor caso (vetor já crescente), as movimentações são mínimas (apenas as comparações, sem deslocamentos).

No insertion sort, para cada elemento a partir do segundo, ele é comparado com os anteriores e deslocado até encontrar a posição correta.

• Melhor caso (vetor já ordenado crescentemente): apenas $n-1$ comparações e $0$ movimentações (cada elemento já está no lugar).

• Pior caso (vetor ordenado decrescentemente): $\frac{n(n-1)}{2}$ comparações e igual número de movimentações (cada elemento percorre toda a parte já ordenada).

A afirmativa inverte os casos: quando "nenhum elemento é maior que seu sucessor" (crescente), temos o menor número de movimentações, não o máximo.

Gabarito oficial: Errado.