Google Search

Monday, April 4, 2011

C++ program for Quick sort


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

void quicksort(int *,int ,int );
int split(int *,int ,int );
int n;
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++;
    
      while(a[q]>i)
q--;

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


      }
   }

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

  
   for(i=0;i<n;i++)
      cout<<" "<<a[i];
   cout<<endl;
   return q;
}

2 comments:

Sengottuvel Sengo said...

Thanks man.... very very usefull for me....

Jayesh Panchal said...

Check out this version of QuickSort Algorithm :)

Quick Sort Program in C

Post a Comment