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)