ESTRUTURA DE DADOS
LES
Método de 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.
São realizados (N-1) passos e no passo “p” os elementos A[1], ..., A[p-1] já estão
ordenados.
Consideraremos que os elementos a serem ordenados estão armazenados nas
posições
e a posição A[0] será utilizada para armazenar um ``sentinela''
(um número inteiro muito pequeno).
No passo “p” o elemento A[p] é comparado com os elementos
Caso A[p] precise ser inserido entre A[j] e A[j+1],
então os elementos A[j+1], ..., A[p-1]são movidos uma posição a
frente e A[p]é inserido na posição correta. A tabela abaixo ilustra
esse processo:
void InsertionSort(int *A, int N)
{
int j,p,temp;
A[0] = MININT
// sentinela - numero inteiro muito pequeno
for (p = 2; p<=N; p++)
{
j = p;
temp = A[p];
while( temp < A[j-1] )
{
A[j] = A[j-1]; // Deslocamento - abre espaço para o elemento a ser inserido
//
j--;
}
A[j] = temp;
// Coloca o elemento na posição correta
}
}