Generate n of random integers in a given range and sort them using quick sort. Apply both binary search and Interpolation search to locate a given integer and compare the search algorithms based on the number of comparisons/probes required for a successful as well as unsuccessful search..
#include<stdlib.h>
#include<conio.h>
#include<stdio.h>
void quicksort(int [10],int,int);
void interpolation(int [10],int,int,int);
main()
{
int x[10],i,n,e;
clrscr();
printf("Enter the Size : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
x[i]=rand()%100;
}
printf("Before Sorting : ");
for(i=0;i<n;i++)
printf("%d\t",x[i]);
quicksort(x,0,n-1);
printf("\nAfter Quick Sorting : ");
for(i=0;i<n;i++)
printf("%d\t",x[i]);
printf("\nEnter the Search Key : ");
scanf("%d",&e);
interpolation(x,0,n-1,e);
b_search(x,0,n-1,e);
getch();
}
void quicksort(int x[10],int first, int last)
{
int pivot,j,temp,i;
if(first<last)
{
pivot=first;
i=first;
j=last;
while(i<j)
{
while(x[i]<=x[pivot]&&i<last)
i++;
while(x[j]>x[pivot])
j--;
if(i<j)
{
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);
}
}
void interpolation(int a[10],int low,int high,int item)
{
int mid,f=0,i,c=0;
printf("\nInterpolation Search :\n");
while(low<=high)
{
c++;
mid=low+(high-low)*((item-a[low])/(a[high]-a[low]));
if(a[mid]==item)
{
printf("\nElements found at POS %d ",mid+1);
f=1;
break;
}
else if(item<a[mid])
high=mid-1;
else
low=mid+1;
}
if(f==0)
printf("\nThe Element is not found");
printf("\nSuccess Comparsions : %d",c);
}
b_search(int a[10],int top,int bot,int item)
{
int mid,flag=0,loc,count=0,i;
printf("\n\nBianary Search Result :\n");
while(top<=bot)
{
count++;
mid=(top+bot)/2;
if(item==a[mid])
{
loc=mid;
flag=1;
break;
}
else if(item<a[mid])
bot=mid-1;
else
top=mid+1;
}
if(flag==1)
printf("\nElement found at POS : %d",loc+1);
else
printf("\nThe Element is not found ");
printf("\nSuccess Comparisions : %d",count);
}
