Insertion Sort ( reverse)

 

Orginal insertion sort will sort elements from starting of the array. This program will sort the elements from end of the array.

/*Insertion Sort*/

#include<stdio.h>
void insertion(int A[], int n);
void print_array(int A[],int n);
main()
{
    int arr[]={7,6,5,4,2,3,1,8,10,9}; // Input Array

    int size = (int)(sizeof(arr)/sizeof(arr[0])); //Calculate size of array

    int itr ; // Iterator

    insertion(arr,size); // Insertion function

    print_array(arr,size);
}

void print_array(int A[], int n)
{
    int itr;

    // Printing array after sorting
    for(itr=0;itr<n;itr++)
    printf("%d ",A[itr]);
}

void insertion(int A[], int n)
{
    int i , j , key;
    for(j=n-1;j>=0;j--)
    {
        key=A[j];
        i=j+1;
        while((i<=n)&&(A[i]<key))
        {
            A[i-1]=A[i];
            i=i+1;
        }
        A[i-1]=key;
    }
}