Insertion Sort Using Interpolation Search

#include<stdio.h>

int Interpolationsearch(int a[50],int n,int key,int start,int end);
main()
{
  int a[50],i,j,n,t,key,item;
  printf("Enter the size of the array:\n");
  scanf("%d",&n);
  printf("Enter elements into the array:");
  for(i=0;i<n;i++)
  {
  	scanf("%d",&a[i]);
  }	
  
  	for(i=1;i<n;i++)
  	{
  		j=i-1;
  		key=a[i];
  		while(a[j]>key&&j>-1)
  		{
  			a[j+1]=a[j];
  			j--;
		  }
		  a[j+1]=key;
	  }
  
printf("The sorted array is: ");
	for(i=0;i<n;i++)
	{
		printf("%d\t",a[i]);
	}
	
	
   printf("\nEnter the element to be searched: ");
   scanf("%d",&item);
	
	int Pos, start=0 , end=n-1;
	
	Pos=Interpolationsearch(a,n,item,start,end);
	if(Pos== -1)
	{
		printf("Element Not Found!!");
	}
	else
	{
		printf("%d found at %d",item,Pos+1);
	}

}

int Interpolationsearch(int a[50],int n,int key,int start,int end) 
{  
	if(start<=end)
	{
		int m=(a[end]-a[start])/(end-start);
		int Pos=start+(key-a[start])/m;
		
		if(a[Pos]==key)
		{
			return Pos;
		}
		else if(a[Pos]>key)
		{
			return Interpolationsearch(a,n,key,start,Pos-1);
		}
		else
		{
			return Interpolationsearch(a,n,key,Pos+1,end);
		}
		return -1;
	}
		
}

     

           

Note: Need to be arranged in compiler after copied

   

 OutPut:

Enter the size of the array: 5 Enter elements into the array:3 6 9 2 4 The sorted array is: 2 3 4 6 9 Enter the element to be searched: 3 3 found at 2