04-08-2012, 01:48 PM
Algorithms Laboratory
Algorithms Laboratory.docx (Size: 54.69 KB / Downloads: 48)
1. Implement Recursive Binary search and linear search and determine the time required to search an element. Repeat the experiment for different values of n, the number of elements in the list to be searched and plot a graph of the time taken versus n.
#include<stdio.h>
#include<conio.h>
#include<time.h>
#define MAX 10
int linsearch(int a[],int n,int key)
{
if(n<0)
return -1;
if(a[n-1]==key)
return n;
else
return linsearch(a,n-1,key);
}
int binsearch(int a[],int n,int low,int high,int key)
{
int mid;
if(low>high)
return -1;
mid=(low+high)/2;
if(key==a[mid])
return mid;
if(key<a[mid])
return binsearch(a,n,low,mid-1,key);
else
return binsearch(a,n,mid+1,high,key);
}
void main()
{
clock_t st1,et1,st2,et2;
int a[MAX],i,n,fd1,fd2,key;
clrscr();
st1=clock();
printf("Enter the size:");
scanf("%d",&n);
printf("Enter the array\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
st2=clock();
printf("Enter the key:");
scanf("%d",&key);
fd1=linsearch(a,n,key);
et1=clock();
if(fd1==-1)
printf("\nLinear search unsuccessful:\n");
else
printf("\nLinear search successful\n");
printf("Time taken for Linear search= %f ns",(et1-st1)/CLOCKS_PER_SEC);
fd2=binsearch(a,n,0,n-1,key);
et2=clock();
if(fd2==-1)
printf("\nBinary search unsuccessful\n");
else
printf("\nBinary search successful\n");
printf("\nTime taken for Binary search= %f ns",(et2-st2)/CLOCKS_PER_SEC);
getch();
}
Output:
Enter the size: 5
Enter the elements:
34 59 108 26 45
Enter the key: 59
Linear search successful
Time taken for Linear search: 8.1330000 ns
Binary search successful
Time taken for Binary search: 1.813400 ns
2. Sort a given set of elements using the Heapsort method and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus n.
#include<stdio.h>
#include<conio.h>
#include<time.h>
void heapify(int a[],int n)
{
int x,y,z,it;
for(z=0;z<=n;z++)
{
it=a[z];
x=z;
y=x/2;
while(y!=0 && it>a[y])
{
a[x]=a[y];
x=y;
y=x/2;
}
a[x]=it;
}
}
void adjust(int a[],int n)
{
int it,x,y;
y=1;
it=a[y];
x=2*y;
while(x<n)
{
if((x+1)<n)
{
if(a[x]<a[x+1])
x++;
}
if(it<a[x])
{
a[y]=a[x];
y=x;
x=2*y;
}
else
break;
}
a[y]=it;
}
void heaps(int a[],int n)
{
int i,temp;
heapify(a,n);
for(i=n;i>=1;i--)
{
temp=a[1];
a[1]=a[i];
a[i]=temp;
adjust(a,i);
}
}
void main()
{
int i,n,a[100];
clock_t st,et;
clrscr();
st=clock();
printf("Enter the number of element:");
scanf("%d",&n);
printf("Enter the elements:\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
heaps(a,n);
et=clock();
printf("The sorted array is\n");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
printf("\nTime taken=%f",(et-st)/CLOCKS_PER_SEC);
getch();
}
Output:
Enter the number of elements: 5
Enter the elements:
10 8 6 3 1
The sorted array is:
1 3 6 8 10
Time taken is: 5.6530541 ns
3. Sort a given set of elements using Merge sort method and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus n.
#include<stdio.h>
#include<conio.h>
#include<time.h>
int c[20],a[20];
void merge(int low,int mid,int high)
{
int i,j,k;
k=i=low;
j=mid+1;
while(i<=mid && j<=high)
{
if(a[i]<a[j])
c[k++]=a[i++];
else
c[k++]=a[j++];
}
while(i<=mid)
c[k++]=a[i++];
while(j<=high)
c[k++]=a[j++];
for(i=low;i<=k-1;i++)
a[i]=c[i];
}
void merge_sort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
merge_sort(mid+1,high);
merge(low,mid,high);
}
}
void main()
{
int i,n;
clock_t st,et;
clrscr();
st=clock();
printf("Enter the size:");
scanf("%d",&n);
printf("Entre the elements\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
merge_sort(0,n-1);
et=clock();
printf("The sorted array is:\n");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
printf("\nTime taken by merge sort=%f ns",(et-st)/CLOCKS_PER_SEC);
getch();
}
Output:
Enter the size: 5
Enter the elements:
3 6 1 8 4
The sorted array:
1 3 4 6 8
The time taken: 6.125847 ns