FC ConcursosFC Concursos

Questão FC331157

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

Linguagens de Programação

FGV · 2023

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.

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
Mostrar resposta e comentário

Gabarito

B

Comentário do professor

O código da letra B implementa a versão do insertion sort que usa uma sentinela em L[0]. Aqui L[0] contém um valor menor que todos os demais, e os elementos a ordenar ocupam posições 1..n.

Para cada índice i em range(2,len(L)) (equivalente ao loop 1-based i=2..n) o algoritmo guarda a chave em v=L[i], inicializa j=i e desloca à direita todos os elementos maiores que v com while L[j-1] > v: fazendo L[j]=L[j-1]; j-=1.

Quando a posição correta é alcançada, insere-se a chave em L[j]=v. A presença da sentinela evita testar o limite inferior (j>0), pois L[0] garante término do while.

O método é in-place, estável e tem complexidade no pior caso \(O(n^2)\), funcionando corretamente para a lista com sentinela proposta.

Conteúdo do catálogo FC Concursos · Atualizado em

Continue aprendendo