# Quick Sort

/***********************************************************

-> This C++ program is to perform Quick sort using recursion

-> This program works in microsoft vc++ 6.0 environment.

-> The numbers are sorted in increasing order.

************************************************************/

#include<iostream.h>

class sorting
{
public:
void input();
void Quicksort(double *,int,int);
void output();
};
double *array;
int n;

void sorting::input()
{
cout<<“****************************************************\n”
<<“This program sorts numbers in increasing order”
<<“\n\t\tusing Quick sort technique\n”
<<“****************************************************\n”;

cout<<“Enter how many numbers you are going to enter for sorting ::”;
cin>>n;
array=new double[n];
for(int i=0;i<n;i++)
cin>>array[i];

Quicksort(array,0,n-1);
}

void sorting::Quicksort(double *a,int l,int r)
{
double t;
if(l>=r)
return;
int i=l;
int j=r+1;
double pivot=a[l];
cout<<“Pivot element is:”<<pivot<<endl;
while(true)
{
do
{i++;}while(a[i]<pivot && i<n);
do
{j–;}while(a[j]>pivot && j<n);
if(i>=j)
break;
t=a[i],a[i]=a[j],a[j]=t;
}
a[l]=a[j];
a[j]=pivot;
Quicksort(a,l,j-1);
Quicksort(a,j+1,r);
}

void sorting::output()
{
cout<<“Now the sorted numbers are ::\n”;
for(int i=0;i<n;i++)
cout<<array[i]<<‘\t’;
cout<<endl;
}

int main()
{
sorting obj;
obj.input();
obj.output();
return 0;
}
/**********************************************************************

SAMPLE OUTPUT ::

****************************************************
This program sorts numbers in increasing order
using Quick sort technique
****************************************************
Enter how many numbers you are going to enter for sorting ::7
1.7
1.6
1.5
1.4
1.3
1.2
1.1
Pivot element is:1.7
Pivot element is:1.1
Pivot element is:1.6
Pivot element is:1.2
Pivot element is:1.5
Pivot element is:1.3
Now the sorted numbers are ::
1.1     1.2     1.3     1.4     1.5     1.6     1.7
Press any key to continue

*************************************************************************/