O Método de ordenação por Inserção Direta é parecido com o modo de se ordenar as cartas em um jogo de pôquer. Inicia-se com a mão esquerda vazia e as cartas viradas com a face para baixo na mesa. Em seguida, remove-se uma carta de cada vez da mesa, inserindo-a na posição correta na mão esquerda.
Para encontrar a posição correta de uma carta, é realizado a comparação da carta retirada da mesa com cada uma das cartas que já estão na mão, da direita para a esquerda. Em cada instante, as cartas seguras na mão esquerda são ordenadas; essas cartas eram originalmente as cartas superiores da pilha na mesa.
Funcionamento:
- Vetor é dividido em 2 subvetores;
- Inicialmente o primeiro segmento contém um único elemento e consequentemente está ordenado. O segundo segmento contém os (n-1) elementos restantes.
- A cada passo, a partir de i=2, o i-ésimo elemento é transferido do segundo segmento para o primeiro segmento, sendo inserido na sua posição apropriada.
Exemplo passo a passo:
Fonte em java utilizando vetor:
public static void ordenacaoInsercaoDireta(int vet[], int tl){
int i, j, chave;
//for – controla os valores que serao inseridos de maneira ordenada
for (i = 0; i<tl; i++){
j = i-1;
chave = vet[i];
while ((j>=0)&&(vet[j]>chave)){
vet[j+1] = vet[j];
j = j-1;
}
vet[j+1]=chave;
}
}
Acesse nosso canal no YouTube para visualizar outros vídeos sobre programação, como por exemplo Python, Java e Desenvolvimento de sistemas comerciais utilizando a linguagem C#.
Material retirado do livro: “Algoritmos Teoria e Pratica – Cormen, Leiserson”.