Insertion Sort

 

#include<stdio.h>

 

#include<stdlib.h>

void swap(int *a ,int *b)

{

int x=*a;

*a=*b;

*b=x;

}

int main()

{

int *a,n,i,j;

printf("\n enter the input array size  .....\t");

scanf("%d",&n);

a=(int *)malloc( sizeof(int)*n);

 

for(i=0;i<n;i++)

a[i]=rand()%(n+1);

//canf("%d",&a[i]);

struct timeval tv_start,tv_end;

gettimeofday(&tv_start,NULL);

 

for(i=1;i<n;i++)

{

int temp=a[i];

for(j=i-1;j>=0&&temp<a[j];j--)

a[j+1]=a[j];

a[j+1]=temp;

 

}

gettimeofday(&tv_end,NULL);

 

for(i=0;i<n;i++)

printf("%d ",a[i]);

 

 

printf("\n------------------------------------------\ntime taken is ..  \t");

printf("%g \n",(tv_end.tv_sec-tv_start.tv_sec)+(tv_end.tv_usec-tv_start.tv_usec)*0.000001);

free(a);

return 0;

}