Trabalho Estrutura de Dados

CENTRO UNIVERSITÁRIO CARIOCA

WAGNER REIS - 2012200681
EDUARDO BESSA DA COSTA 2012101492

INSERÇÃO DIRETA

Rio de Janeiro
2013

WAGNER REIS
EDUARDO BESSA DA COSTA

INSERÇÃO DIRETA

Trabalho de Atividade Supervisionada
Prof. Giselle Batalha
Estrutura de Dados I.

Rio de Janeiro
2013
Inserção
Definição:
Este é o método de ordenação mais rápido entre os métodos básicos. Ele Ordena um vetor da esquerda para a direita, por ordem crescente ou decrescente. À medida que o vetor vai sendo percorrido, ele deixa seus elementos à esquerda ordenados.
Funcionamento:
Percorre um vetor, sempre a partir do primeiro índice desordenado (inicialmente o 2º elemento), e em seguida procura inseri-lo na posição correta, comparando-o com o seu(s) anterior(s) e trocando-os de lugar enquanto ele for menor que seu(s) precedente(s).
Método da Inserção Direta
Um dos métodos mais simples de ordenação é a inserção direta. Inicialmente, são ordenados os 2 primeiros membros do array. Em seguida, é inserido o 3º membro na sua posição ordenada com relação aos 2 primeiros. O processo continua até que todos os elementos estejam ordenados.
Funcionamento - Ordenação crescente:
• São realizados (N-1) passos e no passo “p” os elementos A[1], ..., A[p-1] já estão ordenados.
• No passo p, nós movemos o elemento na posição p para a esquerda, até que seu lugar correto seja encontrado entre os p primeiros elementos.
• O elemento na posição p é salvo em tmp, e todos os elementos maiores são movidos uma casa à direita e, então, tmp é colocado na posição correta.
Exemplo de Ordenação

Algoritmo de Ordenação por Inserção Direta Temos uma sequência destino a1...ai-1 e uma sequência fonte ai...an. Em cada passo, iniciando-se com i = 2 e incrementando-se i de uma em uma unidade, o i-ésimo elemento da sequência vai sendo retirado e transferido para a sequência destino, e inserido na posição apropriada. Sequência fonte: 44 55 12 42 94 18 06 67 I = 2 44 55 12