Questão FC373274
Considere a classe Java abaixo, que usa um método de ordenação por inserção para rearranjar os valores em um vetor em ordem crescente. public class Organiza{ public static void mai
Linguagens de Programação
FCC · 2019
Considere a classe Java abaixo, que usa um método de ordenação por inserção para rearranjar os valores em um vetor em ordem crescente.
public class Organiza{
public static void main(String[] args) {
int k[] = {88, 44, 42, 7, 72, 5};
int n = k.length;
ordena(n, k);
}
static void ordena(int n, int v[]) {
for (int j = 1; j < n; ++j) {
int x = v[j];
int i;
for (..I..){
v[i + 1] = v[i];
}
..II.. ;
}
}
}
Para que a ordenação por inserção ocorra corretamente, as lacunas I e II devem ser corretamente preenchidas com
- i=j-1; i >=0 && v[i]>x; − −i e v[i-1]=x
- i=j-1; i >=0; i++ e v[i+1]=x
- i=j-1; i >=0 && v[i]>x; − −i e v[i+1]=x
- i=j-1; i >=0 && v[i]>x; ++i e v[i]=x
- i=j-1; i >=0 || v[i]>x; − −i e v[i+1]=x
Mostrar resposta e comentário
Gabarito
Certo
Comentário do professor
Na estratégia do insertion sort, o elemento atual é guardado em x e comparamos com os anteriores, deslocando à direita os que forem maiores. Aqui isso é feito com:
i = j - 1; e a condição do laço i >= 0 && v[i] > x, decrescendo i (--i).
Enquanto i >= 0 e v[i] > x, executamos v[i+1] = v[i], que move o valor maior uma posição à direita. A verificação em primeiro lugar de i >= 0 evita acesso fora dos limites do vetor.
Ao sair do laço, i está na posição imediatamente anterior à onde x deve ficar (pode ser -1 se todos os anteriores foram maiores). Por isso atribuímos v[i+1] = x, garantindo que x seja inserido na posição correta (\(i+1\)).
Essa sequência preserva a ordenação parcial à esquerda de j e realiza a inserção estável e correta do elemento atual.
Conteúdo do catálogo FC Concursos · Atualizado em