Wednesday, August 7, 2019

Comparison Between Quick sort And bubble sort In C

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;

}

OUTPUT : 


No comments:

Post a Comment