Quick Sort Description
The quicksort is considered to be very efficient, with its "divide and conquer" algorithm.
This sort starts by dividing the original array into two sections (partitions) based upon the
value of the first element in the array. Since our example sorts into descending order, the
first section will contain all the elements greater than the first element. The second section
will contain elements less than (or equal to) the first element. It is possible for the first
element to end up in either section.
Let's examine our same example:
Array at beginning: 84 69 76 86 94 91
= 1st partition 86 94 91 84 69 76
= 2nd partition 94 91 86 84 69 76
94 91 86 84 69 76
94 91 86 84 69 76
Done: 94 91 86 84 76 69
This sort uses recursion - the process of "calling itself". Recursion will be studied at a
later date.
Quick sort Algorithm
QUICKSORT(A,p,q)
if(p < q)
then r = PARTITION(A,p,q)
QUICKSORT(A,p,r-1)
QUICKSORT(A,r+1,q)
PARTITION(A,p,q)
x = A[p]
i=p
for j = p+1 to q
if A[j] <= x
then i = i+1
swap A[i] with A[j]
swap A[p] with A[i]
return i
Quick Sort Program
#include <iostream>
using namespace std;
void quickSort(int *,int,int);
int partition(int *, int,int);
int main()
{
int A[10]={6,10,13,5,8,3,2,25,4,11};
int p=0,q=10;
cout<<"======Original======="<<endl;
for(int f=0; f<10; f++)
cout<<A[f]<<endl;
quickSort(A,p,q);
cout<<"======Sorted======="<<endl;
for(int f=0; f<10; f++)
cout<<A[f]<<endl;
}
void quickSort(int *A, int p,int q)
{
int r;
if(p<q)
{
r=partition(A, p,q);
quickSort(A,p,(r-1)); //I think the problem is here this first quickSort call
// is reducing the value of r and hence value of q becomes
// less than p recursively. How can I separate both calls
// one for left and one for right sub array of the pivot.
quickSort(A,(r+1),q);
}
}
int partition(int *A, int p,int q)
{
int x= A[p];
int i=p;
int temp;
int j;
for(j=p+1; j<q; j++)
{
if(A[j]<=x)
{
i=i+1;
temp= A[j];
A[j]=A[i];
A[i]=temp;
}
temp= A[p];
A[p]=A[i];
A[i]=temp;
return i;
}
