O algoritmo conhecido como insertion (inserção) é um dos mais conhecidos algoritmos de sort. Para um conjunto de chaves num array, o primeiro elemento é uma espécie de sentinela, e recebe um valor menor do que o menor elemento do array a ser ordenado. A lista de entrada [-1,2,4,10,5,3,11], por exemplo, seria rearranjada para [-1, 2, 3, 4, 5, 10, 11]. Assinale o código Python que executa corretamente esse algoritmo.
- A)def inserção(L): for i in range(0,len(L)): v = L[i]; j = i; while L[j-1] > v: L[j] = L[j-1] j -= 1 L[j] = v
Errada: comeca no indice 0 e tenta comparar a sentinela com L[j-1], o que quebra a logica do insertion sort com sentinela.
- B)def inserção(L): 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
Certa: faz a insercao ordenada usando a sentinela no indice 0, percorre a partir do inicio adequado e desloca os maiores para a direita.
- C)def inserção(L): 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
Errada: usa o operador de desigualdade incorreto, incrementa j no sentido errado e nao respeita a logica do deslocamento para tras.
- D)def inserção(L): for i in range(1,len(L)-1): v = L[i]; j = i; while L[j-1] <= v: L[j] = L[j-1] continue L[j] = v
Errada: o laço usa a condicao invertida (<=), entra em comportamento inadequado e ainda nao faz a insercao corretamente.
- E)def inserção(L): for i in range(2,len(L) -1): v = L[i]; j = i; while L[j-1] > v: L[j] = L[j-1] j -= 1 continue L[i] = v
Errada: embora tenha a ideia de deslocar elementos, o intervalo do for esta errado, ha continue fora de lugar e a insercao final em L[i] nao corresponde ao passo do algoritmo.
Gabarito: B
O insertion sort funciona como quando voce organiza cartas na mao: pega um elemento por vez e vai encaixando no lugar certo da parte ja ordenada. Nesse algoritmo, a ideia e manter um prefixo ordenado e, a cada nova chave, deslocar para a direita os elementos maiores ate abrir espaco para a insercao. No enunciado, o primeiro elemento e uma sentinela, ou seja, um valor menor do que todos os demais. Isso evita testar limites a cada comparacao, porque o algoritmo pode comparar com L[j-1] sem medo de “passar do comeco” da lista. Em livros de algoritmos, essa variacao e bem classica e aparece justamente para simplificar o laço interno. A alternativa B esta correta porque percorre a lista a partir do indice 2, preserva a sentinela na posicao 0 e, para cada v, desloca enquanto L[j-1] for maior que v, inserindo depois v na posicao adequada. Essa e exatamente a mecanica do insertion sort com sentinela. As demais alternativas erram o ponto de partida, o sentido da comparacao, o incremento/decremento de j ou ate a atribuicao final. Em resumo: o algoritmo certo precisa andar para tras com j -= 1 e parar quando achar um elemento menor ou igual a chave, deixando a lista ordenada passo a passo.