No método de ordenação por inserção (insertion sort) devemos inicialmente ordenar os dois primeiros elementos. Depois inserimos o terceiro elemento na posição ordenada em relação aos dois primeiros. Depois inserimos o quarto elemento em sua posição ordenada em relação aos três já posicionados, e assim por diante até que todo o vetor esteja ordenado.
Vamos a um exemplo prático. Dado nosso vetor:
[ 4 ][ 5 ][ 1 ][ 3 ][ 2 ]
Vamos ordená-lo em ordem crescente pelo método da inserção:
Primeiro nosso programa ordenaria os dois primeiros elementos do vetor, “4″ e “5″ que, neste caso, já estão ordenados:
[ 4 ][ 5 ][ ][ ][ ]
Depois o programa pegaria o terceiro elemento do vetor, no caso “1″, e o introduziria na posição ordenada em relação aos dois primeiros:
[ 1 ][ 4 ][ 5 ][ ][ ]
Depois o programa pegaria o quarto elemento, no caso “3″, e o introduziria na posição ordenada em relação aos três primeiros:
[ 1 ][ 3 ][ 4 ][ 5 ][ ]
Depois o programa pegaria o quinto elemento, neste caso “2″, e o introduziria na posição ordenada em relação aos quatro primeiros:
[ 1 ][ 2 ][ 3 ][ 4 ][ 5 ]
Pronto, nosso vetor está ordenado.
Abaixo você pode ver uma codificação em C para a resolução deste problema:
#include <stdio.h>
int main()
{
int vetor1[5] = {4,5,1,2,3};
int vetor2[5];
int c,c2,c3;
int ok = 0;
/* ordenando os dois primeiros elementos */
if(vetor1[0] < vetor1[1])
{
vetor2[0] = vetor1[0];
vetor2[1] = vetor1[1];
}
else
{
vetor2[0] = vetor1[1];
vetor2[1] = vetor1[0];
}
/* ordenando os outros elementos */
for(c = 2;c < 5; c++)
{
/* introduzindo vetor1[c] no vetor2 */
ok = 1; /* considera vetor2 não ordenado */
/* verifica se algum elemento de vetor2
é maior que vetor1[c] */
for(c2 = 0;c2 < c;c2++)
{
if(vetor2[c2] > vetor1[c])
{
/* joga os elementos de vetor2 para frente */
for(c3 = c;c3 > c2;c3--)
vetor2[c3] = vetor2[c3 - 1];
/* insere vetor1[c] em sua posição ordenada */
vetor2[c2] = vetor1[c];
ok =0; /* considera vetor2 ordenado */
break;
}
}
/* se nenhum elemento de vetor2
é maior que vetor1[c] ... */
if(ok == 1)
vetor2[c] = vetor1[c];
}
for(c = 0;c < 5;c++)
printf("%d ",vetor2[c]);
printf("\n");
return(0);
}
Hoje eu deixo a codifição Python (ou em outra linguagem que você goste) para vocês.
Um grande abraço e bons estudos.
Samuel