Questão de Algoritmos e Estrutura de Dados — Algoritmos de Ordenação — FGV 2023

Insertion Sort com Sentinela (Python)

Gabarito: letra B. A implementação correta do insertion sort com sentinela deve iniciar o laço em range(2, len(L)), pois o índice 0 é a sentinela (menor que todos) e o índice 1 já está ordenado. O laço interno deve deslocar para a direita todos os elementos maiores que a chave atual (v) e, ao final, posicionar v no lugar correto. A alternativa B atende exatamente a esses requisitos.

A questão testa o conhecimento do algoritmo de ordenação por inserção com a presença de uma sentinela. A lista de exemplo [-1,2,4,10,5,3,11] mostra que o primeiro elemento (-1) é uma sentinela menor que todos os demais. Dessa forma, o algoritmo não precisa tratar o índice 0 como um elemento normal; o loop principal começa a partir do índice 2 (ignorando o índice 1, que já está ordenado com a sentinela). A cada iteração, o elemento atual (v) é comparado com os anteriores; enquanto houver elementos maiores, eles são deslocados uma posição para a direita, liberando espaço para v.

Alternativa A — ❌ Incorreta

for i in range(0, len(L)):

O laço começa em i = 0, ou seja, tenta inserir a própria sentinela. Isso quebra a lógica do algoritmo, pois a sentinela não deve ser movida. Além disso, o índice j-1 para i=0 acessaria L[-1], causando erro ou comportamento inesperado.

Alternativa B — ✅ Correta ⟵ GABARITO

for i in range(2, len(L)):
    v = L[i]
    j = i
    while L[j-1] > v:
        L[j] = L[j-1]
        j -= 1
    L[j] = v

O laço começa em i = 2, pulando a sentinela e o primeiro elemento real (que já está ordenado). A condição L[j-1] > v garante que apenas elementos maiores que v sejam deslocados; a sentinela (menor que todos) interrompe o loop no pior caso. A atribuição final L[j] = v insere o valor na posição correta. A saída para a lista de exemplo será exatamente [-1, 2, 3, 4, 5, 10, 11].

Alternativa C — ❌ Incorreta

Utiliza while L[j-1] <> v (diferente de) em vez de >. Isso deslocaria elementos até encontrar um igual, o que não ordena corretamente. Além disso, j += 1 faz com que o índice se mova para a direita, em vez de para a esquerda, causando deslocamento na direção errada. A sintaxe <> também não é comum em Python (equivale a !=).

Alternativa D — ❌ Incorreta

O laço for i in range(1, len(L)-1) começa em i=1 (ignorando a sentinela) mas termina em len(L)-2, deixando o último elemento de fora. A condição while L[j-1] <= v desloca elementos mesmo quando são iguais, o que muda a ordenação de estável para instável e, com sentinela, poderia causar deslocamentos desnecessários. O uso de continue dentro do while é desnecessário e não altera a lógica, mas o erro principal é a condição e o alcance do laço.

Alternativa E — ❌ Incorreta

O laço for i in range(2, len(L)-1) começa em i=2 mas termina em len(L)-2, excluindo o último elemento. A atribuição final é L[i] = v em vez de L[j] = v, o que não posiciona o elemento no local correto após os deslocamentos. O continue também é redundante.

Gabarito: letra B.