Insertion sort in the opposite direction. Sorted portion to the right and unsorted to the left

Question

I am trying to inverse the sorted portion and unsorted portion in the insertion sort logic described in CLR. The output is completely erroneous. Can somebody point the mistake or logic error in my code.

#include<stdio.h>
#include<stdlib.h>

int main()
{   int a[] = {67,7,3,2,1,9,45,5};
    int k;
    int n = sizeof(a)/sizeof(a[0]);
    insert(a,n);
    for(k = 0;k < n; k++)
        printf("%d %d\n",k,a[k]);
    return 0;
}

void insert(int *a,int n)
{
    int i,j,val;
    for(i=n-2;i>=0;i--){
        val=a[i];
        for(j=i+1;j<n && a[j]<val;j++){
            a[j-1]=a[j];
        }
        a[j--]=val;
}

Answer 1

You should insert the last element at a[j - 1]. You can achieve this with a decrement, but in that case you must use a prefix decrement, which changes the value before referencing it: a[--j] = val;.

Here's a corrected version:

void insertion_sort_backwards(int *a, int n)
{
    int i = n - 1;

    while (i--) {
        int val = a[i];
        int j;

        for (j = i + 1; j < n && a[j] < val; j++) {
            a[j - 1] = a[j];
        }

        a[j - 1] = val;
    }
}

This will sort your array from the right:

67, 7, 3, 2, 1, 9, 5, 45
67, 7, 3, 2, 1, 5, 9, 45
67, 7, 3, 2, 1, 5, 9, 45
67, 7, 3, 1, 2, 5, 9, 45
67, 7, 1, 2, 3, 5, 9, 45
67, 1, 2, 3, 5, 7, 9, 45
1, 2, 3, 5, 7, 9, 45, 67