O algoritmo conhecido como insertion (inserção) é um dos mai...

Próximas questões
Com base no mesmo assunto
Q2287690 Algoritmos e Estrutura de Dados
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.
Alternativas

Gabarito comentado

Confira o gabarito comentado por um dos nossos professores

Alternativa Correta: B

Vamos entender o funcionamento do algoritmo de inserção (insertion sort) e analisar as alternativas.

O algoritmo de insertion sort é conhecido por ser simples e eficiente para pequenas listas ou listas quase ordenadas. Ele funciona da seguinte maneira:

1. Percorre a lista de elementos, começando do segundo elemento até o último.

2. Para cada elemento, compara-o com os elementos anteriores e insere-o na posição correta, de modo a manter os elementos já percorridos ordenados.

Com isso em mente, vamos analisar cada alternativa.

Alternativa A:

O loop começa em range(0, len(L)), o que significa que o primeiro elemento também será considerado no processo de ordenação. No entanto, o primeiro elemento já é a nossa "sentinela" e não deveria ser movido. Esse detalhe invalida a alternativa.

Alternativa B (Correta):

O loop começa em range(2, len(L)). Isso significa que o primeiro elemento (índice 0) é a sentinela e é ignorado. A partir do segundo elemento (índice 1), o algoritmo começa a comparação e deslocamento. Aqui, a lógica do algoritmo de inserção está correta:

  • Armazena o valor do elemento atual em v.
  • Compara v com os elementos anteriores, deslocando os maiores para a direita.
  • Insere v na posição correta.

Portanto, essa é a alternativa que implementa corretamente o algoritmo de inserção.

Alternativa C:

Embora o loop comece corretamente em range(2, len(L)), o teste de condição while L[j-1] <> v está incorreto, pois o correto seria verificar se L[j-1] > v. Além disso, o incremento de j com j += 1 não é a operação esperada, já que j deveria ser decrementado para localizar a posição correta. Esses erros tornam a alternativa inválida.

Alternativa D:

O loop inicia em range(1, len(L) - 1), o que exclui o último elemento do array, não sendo considerado no processo de ordenação. Além disso, a condição while L[j-1] <= v é incorreta, pois deveria ser while L[j-1] > v para garantir a ordenação correta. A estrutura do loop está incorreta, invalidando a alternativa.

Alternativa E:

Embora o loop comece corretamente em range(2, len(L) - 1), ele não percorre todo o array, excluindo o último elemento. A linha final L[i] = v está incorreta, pois deveria ser L[j] = v, colocando o valor de volta na posição correta. Estes erros tornam a alternativa inválida.

Em resumo, a alternativa B é a única que implementa corretamente o algoritmo de inserção (insertion sort) conforme descrito no enunciado da questão.

Clique para visualizar este gabarito

Visualize o gabarito desta questão clicando no botão abaixo

Comentários

Veja os comentários dos nossos alunos

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

   O loop for i in range(2, len(L)): percorre a lista a partir do índice 2. Isso está correto, pois o algoritmo de ordenação por inserção geralmente começa a partir do segundo elemento.

   Dentro do loop, v = L[i] armazena o valor atual que está sendo considerado para a ordenação.

   j = i inicializa a variável j com o índice atual.

   O loop while L[j-1] > v: percorre os elementos à esquerda de v até encontrar a posição correta para inseri-lo.

   L[j] = v insere o valor v na posição correta no array.

Portanto, o código segue o algoritmo de ordenação por inserção corretamente, movendo-se através da lista e inserindo cada elemento na posição correta à medida que avança. As outras opções têm problemas como erros de lógica, índices incorretos, ou comparações inadequadas, o que as torna incorretas para o propósito de ordenação por inserção.

Alternativa: B

Mas se começar a partir do índice 2 não estaria começando pelo 3° elemento da lista?

A questão afirma que a primeira posição do vetor, no caso -1, é um sentinela, e deve ser ignorado.

Clique para visualizar este comentário

Visualize os comentários desta questão clicando no botão abaixo