Descreva um algoritmo que insere um número inteiro
na posição apropriada na lista
de números inteiros que está em ordem crescente.
Passo 1
O problema pede um método para inserir um inteiro
em um vetor
que já está ordenado em ordem crescente, de modo que o vetor resultante continue ordenado. O conteúdo aqui é manipulação de arrays e deslocamento de elementos para “abrir espaço” e colocar
na posição correta.
Passo 2
Para manter a eficiência e a simplicidade, vamos usar uma busca linear de trás para frente: começamos em
e comparamos
com
. Enquanto
, deslocamos
para a posição
e decrementamos
. Quando sairmos desse laço, teremos encontrado a posição certa onde
deve ficar.
Passo 3
Ao final do laço de deslocamento, o índice
aponta para o último elemento que é menor ou igual a
(ou zero, se todos forem maiores). Portanto, devemos inserir
em
, mantendo a ordenação.
Passo 4
Esse procedimento desloca no máximo
elementos (caso
seja o menor), e insere
corretamente, garantindo complexidade
no pior caso e mantendo o vetor ordenado.
Resposta
Função Inserir
,