Flashcard FC331351
Como a sentinela em L[0] permite omitir o teste do limite inferior no insertion sort?
Linguagens de Programação
FGV · 2023
Como a sentinela em L[0] permite omitir o teste do limite inferior no insertion sort?
Mostrar resposta e comentário
Resposta
A sentinela em L[0] contém um valor menor que todos os demais, garantindo que o while que desloca elementos termine sem verificarj>0.Explicação:
Para cada
i em range(2,len(L)) guarda-se v = L[i] e inicializa-se j = i.Enquanto
L[j-1] > v faz-se L[j] = L[j-1] e j -= 1.A presença da sentinela em L[0] assegura o término do while ao ser alcançada.
O método é in-place, estável e tem complexidade no pior caso
O(n^2).Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/331157
Conteúdo do catálogo FC Concursos · Atualizado em