Insertion sort using cpp.

Insertion sort using CPP.

In this tutorial we learn another sorting technique that is insertion sort.
this technique comparing element in the array each other and then when smaller element is found then
change to its proper position.
complexity:
worst complexity:n^2
average complexity:n^2
best complexity:n

example:
 
we are sorting this array element in ascending order.
suppose we have a unsorted array of element 5
arr[5]=43 25 12 73 39

//in the first iteration compare 1st and 2nd position in array if smaller element is found then change to its proper position.
//after iteration first array become
arr[5]=25 43 12 73 39

//after first iteration compare 1st and 2nd position of element with 3rd position of element and then sort element.
//after iteration array become.
arr[5]=12 25 43 73 39

//now compare all previous element with 4th position of element.
in this iteration no change because no smaller element is found.
array element become as it is.

//for last iteration it compare all previous positin with 5th position of element.
array become.
arr[5]=12 25 39 43 73

//finally we get a sorted array in ascending order.

This is the simple code for sort array in ascending order by using insertion sort.
     
#include<iostream.h>
#include<conio.h>
//declare the function for insertion sort.
void insertsort(int *arr,int size)
{
    int i,j,index;
    for(i=1;i<size;i++)
    {
        index=arr[i];
        j=i;
        while((j>0)&&(arr[j-1]>index))
        {
            arr[j]=arr[j-1];
            j=j-1;
        }
        arr[j]=index;
    }
}
void main()
{
    int *arr,size;
    clrscr();
    //Enter array size dynamically. 
    cout<<"\nEnter the size of array:";
    cin>>size;
    cout<<"\nEnter the element:";
    for(int i=0;i<size;i++)
    {
        cin>>arr[i];
    }
    insertsort(arr,size);
    cout<<"\nSorted element are:";
    for(i=0;i<size;i++)
    {
        cout<<arr[i]<<"\n";
    }
    getch();
}

OUTPUT: