PROGRAM :
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void bubble_sort(int *ar,int length);
void quick_sort(int *ar,int l,int u);
int partition(int *ar, int l,int u);
void swap(int a[],int i,int j);
int main()
{
int i,j,k,*ab,*aq,size;
int n[]={40,60,100,200,5000,10000,20000,50000,80000,100000};
int l=10;
clock_t begin, end;
double time_bubble, time_quick;
srand(time(NULL));
printf("\n Input size Time For Quick Sort Time For Bubble Sort \n\n");
for(j=0;j<l;j++)
{
size=n[j];
ab=(int *)malloc(sizeof(int)*n[j]);
aq=(int *)malloc(sizeof(int)*n[j]);
for(i=0;i<size;i++)
{
k = rand()%(size + 1);
ab[i]=k;
aq[i]=k;
}
begin=clock();
bubble_sort(ab,size);
end=clock();
time_bubble=((double)(end-begin)/CLOCKS_PER_SEC);
begin=clock();
quick_sort(aq,0,size-1);
end=clock();
time_quick=((double)(end-begin)/CLOCKS_PER_SEC);
printf(" %d\t\t\t%0.10f\t\t\t%0.10f\n", size, time_quick, time_bubble);
}
return 0;
}
void bubble_sort(int *ar, int n)
{
int i,j,flag=0,tmp;
for(i=0;i<n-1;i++)
{
flag=0;
for(j=0;j<n-i-1;j++)
{
if(ar[j]>ar[j+1])
{
flag=1;
tmp=ar[j];
ar[j]=ar[j+1];
ar[j+1]=tmp;
}
}
if( flag==0)
break;
}
}
void quick_sort(int *arr,int l,int u)
{
int p;
if(l<u)
{
p=partition(arr,l,u);
quick_sort(arr,l,p-1);
quick_sort(arr,p+1,u);
}
}
void swap(int *arr,int i,int j)
{
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
int partition(int *arr,int l,int u)
{
int i;
int p=l;
int pivot=arr[p];
for(i=l+1;i<=u;i++)
{
if(arr[i]<pivot)
swap(arr,i,++p);
}
swap(arr,l,p);
return p;
}
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void bubble_sort(int *ar,int length);
void quick_sort(int *ar,int l,int u);
int partition(int *ar, int l,int u);
void swap(int a[],int i,int j);
int main()
{
int i,j,k,*ab,*aq,size;
int n[]={40,60,100,200,5000,10000,20000,50000,80000,100000};
int l=10;
clock_t begin, end;
double time_bubble, time_quick;
srand(time(NULL));
printf("\n Input size Time For Quick Sort Time For Bubble Sort \n\n");
for(j=0;j<l;j++)
{
size=n[j];
ab=(int *)malloc(sizeof(int)*n[j]);
aq=(int *)malloc(sizeof(int)*n[j]);
for(i=0;i<size;i++)
{
k = rand()%(size + 1);
ab[i]=k;
aq[i]=k;
}
begin=clock();
bubble_sort(ab,size);
end=clock();
time_bubble=((double)(end-begin)/CLOCKS_PER_SEC);
begin=clock();
quick_sort(aq,0,size-1);
end=clock();
time_quick=((double)(end-begin)/CLOCKS_PER_SEC);
printf(" %d\t\t\t%0.10f\t\t\t%0.10f\n", size, time_quick, time_bubble);
}
return 0;
}
void bubble_sort(int *ar, int n)
{
int i,j,flag=0,tmp;
for(i=0;i<n-1;i++)
{
flag=0;
for(j=0;j<n-i-1;j++)
{
if(ar[j]>ar[j+1])
{
flag=1;
tmp=ar[j];
ar[j]=ar[j+1];
ar[j+1]=tmp;
}
}
if( flag==0)
break;
}
}
void quick_sort(int *arr,int l,int u)
{
int p;
if(l<u)
{
p=partition(arr,l,u);
quick_sort(arr,l,p-1);
quick_sort(arr,p+1,u);
}
}
void swap(int *arr,int i,int j)
{
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
int partition(int *arr,int l,int u)
{
int i;
int p=l;
int pivot=arr[p];
for(i=l+1;i<=u;i++)
{
if(arr[i]<pivot)
swap(arr,i,++p);
}
swap(arr,l,p);
return p;
}
OUTPUT :
No comments:
Post a Comment