Questão de Algoritmos e Estrutura de Dados — Algoritmos — UFSC 2022
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq808673
Banca
UFSC
Órgão
UFSC
Ano
2022
Nível
Médio
Cargo
Técnico de Tecnologia da Informação
Considere o pseudocódigo do método de ordenação Insertion Sort, o qual ordena em ordem crescente os números naturais armazenados em um vetor (array) v de tamanho t indexado a partir de zero (ou seja, índices do vetor variam de 0 a t-1).Assinale a alternativa que completa corretamente o espaço pontilhado entre chaves do pseudocódigo abaixo.função Ordena(v, t) { i ← 1 enquanto i < t faça { j ← i enquanto j > 0 e v[j-1] > v[j] faça { ..................... } i ← i + 1 } }
Ax ← v[j]v[j] ← v[j - 1]v[j – 1] ← xj ← j + 1
Bx ← v[j]v[j] ← v[j - 1]v[j – 1] ← xj ← j - 1
Cx ← v[j]v[j] ← v[j + 1]v[j + 1] ← xj ← j - 1
Dx ← v[j]v[j] ← v[j + 1]v[j + 1] ← xj ← j + 1
Ex ← v[j]v[j] ← v[j - 1]v[j – 1] ← xj ← j – 2
Revelar gabarito e comentário▾
GabaritoB — x ← v[j]
v[j] ← v[j - 1]
v[j – 1] ← x
j ← j - 1
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Insertion Sort – Troca e decremento
Gabarito: letra B. O trecho correto para o Insertion Sort é: armazenar v[j] em x, copiar v[j-1] para v[j], colocar x em v[j-1] e decrementar j (j ← j-1). Esse padrão realiza a troca entre elementos adjacentes e move o índice para trás, permitindo que o elemento "flutue" até sua posição ordenada.
O Insertion Sort percorre o vetor da esquerda para a direita. Para cada posição i, o elemento v[i] é inserido na parte já ordenada (índices 0 a i-1) por meio de trocas sucessivas com o vizinho anterior enquanto ele for maior. O loop interno (j) deve começar em i e decrementar a cada troca.
1Armazena v[j] em x
2Copia v[j-1] para v[j]
3Coloca x em v[j-1]
4Decrementa j (j ← j-1)
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Executa a troca correta (v[j] ↔ v[j-1]), mas incrementa j (j ← j + 1). Isso faria o índice avançar para a direita, saindo da região ordenada e quebrando o algoritmo.
Alternativa B — ✅ Correta ⟵ GABARITO
Realiza a troca padrão com auxiliar x e decrementa j (j ← j - 1). Essa é a sequência exata do Insertion Sort: troca os elementos e move o índice para a esquerda para continuar comparando.
Alternativa C — ❌ Incorreta
Troca v[j] com v[j+1] (em vez de v[j-1]), o que desloca o elemento para a direita, e depois decrementa j. Isso não insere o elemento na posição correta; na verdade, empurraria o elemento maior para a frente.
Alternativa D — ❌ Incorreta
Troca v[j] com v[j+1] (erro de índice) e incrementa j, afastando-se ainda mais da lógica correta.
Alternativa E — ❌ Incorreta
Troca correta entre v[j] e v[j-1], mas decrementa j em 2 (j ← j – 2). Isso pularia um elemento, possivelmente deixando o vetor desordenado.
NÃO CAIA NESSA!
A banca explora a confusão entre incrementar e decrementar o índice j, e também a troca com v[j+1] em vez de v[j-1]. Lembre-se: no Insertion Sort o elemento "anda para trás" → j diminui.