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;
    }
}

Insertion Sort (orginal)

 

/*Insertion Sort*/

#include<stdio.h>
void insertion(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

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

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

Output:

1 2 3 4 5 6 7 8 9 10

 

Time Complexity: O(n^2)