Wednesday, 28 November 2012

Quick Sort algorithm with time complexity calculation


//A program to implement Quick Sort algorithm. Also calculate time complexity.
#include<stdio.h>
#include<conio.h>
int x,r,p,a[20],i,j,n,temp,count=0;

int partition(int p,int r)
{
 x=a[r];
 i=p-1;
 for(j=p;j<=r-1;j++)
 {
  if(a[j]<=x)
  {
   i=i+1;
   temp=a[i];
   a[i]=a[j];
   a[j]=temp;count+4;
  }
  count++;
  }
   temp=a[i+1];
   a[i+1]=a[r];
   a[r]=temp;
   count+3;
 return(i+1);
}

void quick_sort(int p,int r)
{
 int q;
 if(p<r)
 {
  q=partition(p,r);
  quick_sort(p,q-1);
  quick_sort(q+1,r);
 }
}

void main()
{ textbackground(1);
 clrscr();
 printf("Enter no.of values: ");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
  printf("value %d:",i);
  scanf("%d",&a[i]);
  count++;
 }
 p=1;
 r=n;
 quick_sort(p,r);
 printf("Sorted using Quick Sort:-\n");
 for(i=1;i<=n;i++)
 {
  printf("%d\t",a[i]);count++;
 }
 printf("\nEs algo ki complexity '%d' hai...\ntumhare ki kitni hai",count);
 printf("\n Enter tumhari algo complexity: ");
 scanf("%d",&i);
 if(i<count) printf("\nMA KASAM,Tumhari algo meri algo se acchi hai");
 else printf("\nMA KASAM,Meri algo tumhari algo se acchi  hai");
 getch();
}
//program written by Mars.

1 comment:

You are welcome, your comment helps me to make this blog more better.