Algoritmos de Ordenação #3 – Inserção Direta

Padrão


Mais um algoritmo de ordenação, dessa vez o algoritmo de Inserção Direta ou Insertion Sort. Este algoritmo é bastante eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados.

Segue, então, a minha implementação em C deste algoritmo:

void insercaoDireta(int *vetor, int tamanho)
{
   int i, x, k, j;

   for(i = 1; i < tamanho; ++i)
   {
      x = vetor[i];
      k = 0;
      j = i - 1;
      while(j >= 0 && k == 0)
      {
         if(x < vetor[j])
         {
            vetor[j + 1] = vetor[j];
            --j;
         }
         else
            k = j + 1;
      }
      vetor[k] = x;
   }
}