## 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