Descreva um algoritmo que insere um número inteiro x na posição apropriada na lista a_{1}, a_{2}, \ldots, a_{n} de números inteiros que está em ordem crescente.

Passo 1

O problema pede um método para inserir um inteiro x em um vetor a_{1},a_{2},\dots,a_{n} 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 x 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 i = n e comparamos a_{i} com x. Enquanto a_{i} > x, deslocamos a_{i} para a posição i+1 e decrementamos i. Quando sairmos desse laço, teremos encontrado a posição certa onde x deve ficar.

Passo 3

Ao final do laço de deslocamento, o índice i aponta para o último elemento que é menor ou igual a x (ou zero, se todos forem maiores). Portanto, devemos inserir x em a_{i+1}, mantendo a ordenação.

Passo 4

Esse procedimento desloca no máximo n elementos (caso x seja o menor), e insere x corretamente, garantindo complexidade O(n) no pior caso e mantendo o vetor ordenado.

Resposta

Função Inserir a[1\ldots n], x \;\;i \leftarrow n \;\;\textbf{while}\;i \ge 1\;\wedge\;a[i] > x\;\textbf{do} \;\;\;\;a[i+1] \leftarrow a[i] \;\;\;\;i \leftarrow i - 1 \;\;\textbf{end while} \;\;a[i+1] \leftarrow x \;\;\textbf{return}\;a[1\ldots n+1]

Exercícios de Livros Relacionados