Insertion Sort - Linguagem C

O método Insertion Sort é simples e bem mais eficiente que os outros métodos vistos: Bubble Sort e Selection Sort.

Um exemplo clássico ao explicar este método é o de ordenar um baralho passando as cartas da mão direita para a mão esquerda passando carta por carta.

#define TAM 10
void insertion_sort(int v[])
{
    int i, j, aux;
    for(i = 1; i < TAM; i++)
    {
        aux = v[i];
        j = i - 1;
        while((j >= 0) && (aux < v[j]))
        {
            v[j+1] = v[j];
            j--;
        }
        v[j+1] = aux;
    }
}

main()
{
    int i, vet[TAM] = {10,9,3,6,7,5,1,8,4,2};
    printf("Vetor atual: ");
    for(i = 0; i < TAM; i++)
        printf("%d ", vet[i]);
    printf("\n");
    system("pause");
    insertion_sort(vet);
    printf("\n\nVetor ordenado: ");
    for(i = 0; i < TAM; i++)
        printf("%d ", vet[i]);
    printf("\n");
    system("pause");
    return 0;
}

Neste método a quantidade de iterações dependerá de quão desordenado está o vetor.
Para verificar a quantidade de iterações podemos criar uma variável global e mandar incrementa-la a cada vez que entrar no laço for e no laço while e mandar imprimi-la no final para ver o resultado.
Dessa forma:

#define TAM 10
int k = 0;
void insertion_sort(int v[])
{
    int i, j, aux;
    for(i = 1; i < TAM; i++)
    {
        aux = v[i];
        j = i - 1;
        while((j >= 0) && (aux < v[j]))
        {
            v[j+1] = v[j];
            j--;
            k++;
        }
        v[j+1] = aux;
        k++;
    }
}

main()
{
    int i, vet[TAM] = {10,9,3,6,7,5,1,8,4,2};
    printf("Vetor atual: ");
    for(i = 0; i < TAM; i++)
        printf("%d ", vet[i]);
    printf("\n");
    system("pause");
    insertion_sort(vet);
    printf("\n\nVetor ordenado: ");
    for(i = 0; i < TAM; i++)
        printf("%d ", vet[i]);
    printf("\nk = %d",k);
    system("pause");
    return 0;
}

O resultado neste caso é 42 iterações. Pode parecer pouco, mais quando aumentamos a quantidade de posições do vetor a diferença aumenta.