quicksort.cpp

quick sort is a sorting algorithm used for sorting data

#include<iostream.h>
#include<conio.h>

void quicksort(int *,int ,int );
int split(int *,int ,int );
int n;

void display(int *a , int n)
{
     int i;
     printf("\narray is : ");
     for(i=0;i<n;i++)
            printf(" %d ",a[i]);
}

int main()
{
   
   int *a;
   int i;
   cout<<"\nenter n : ";
   cin>>n;
   a=new int[n];
   cout<<"\n\nEnter the values to sort : \n";
   for(i=0;i<n;i++)
   {
      cin>>a[i];
   }

   cout<<"\nBefore sorting : ";
   for(i=0;i<n;i++)
      cout<<" "<<a[i];

   //cout<<"\nVarious steps involved are :\n ";
   quicksort(a,0,n-1);

   cout<<"\nArray after sorting : ";

   for(i=0;i<n;i++)
      cout<<" "<<a[i];

   getch();
   return 0;
}

void quicksort(int a[],int lower,int upper)
{
   int i;
   
   if(upper>lower)
   {
      i=split(a,lower,upper);
     

      quicksort(a,lower,i-1);
    
      quicksort(a,i+1,upper);
   }

}

int split(int a[],int lower,int upper)
{
   int i,p,q,temp;
   p=lower+1;
   q=upper;
   i=a[lower];

   while(q>=p)
   {
      
      while(a[p]<i && p <= upper)
	       p++;
      
      while(a[q]>i && q >= 0)
	       q--;

      if(q>p)
      {
	      temp=a[p];
	      a[p]=a[q];
	      a[q]=temp;

      }
   }

   temp=a[lower];
   a[lower]=a[q];
   a[q]=temp;

   display(a , n);
   printf("   p = %d , q = %d",p,q);
   return q;
}