Your consideration is wrong. The value of r
does not change, since it is given as value to the Quicksort function(not a reference).
You handle the ranges with p
,q
such that p
is the first index in the range and q
the first index not in the range.
Thus, your calls were wrong:
r=partition(A, p,q);
quickSort(A,p,r); //range is from A[p] to A[r-1]
quickSort(A,(r+1),q); //range is from A[r+1] to A[q-1]
Here is the complete example. I used std::swap to change elements and ans std::vector instead of an array.
#include <iostream>
#include <vector>
using namespace std;
void quickSort(vector<int>&,int,int);
int partition(vector<int>&, int,int);
int main()
{
vector<int> A = {6,10,13,5,8,3,2,25,4,11};
int p=0;
int q=10;
cout<<"======Original======="<<endl;
for(auto e: A)
cout<< e <<" ";
cout<< endl;
quickSort(A,p,q);
cout<<"======Sorted======="<<endl;
for(auto e: A)
cout<< e <<" ";
cout<< endl;
}
void quickSort(vector<int>& A, int p,int q)
{
int r;
if(p<q)
{
r=partition(A, p,q);
quickSort(A,p,r);
quickSort(A,r+1,q);
}
}
int partition(vector<int>& A, int p,int q)
{
int x= A[p];
int i=p;
int j;
for(j=p+1; j<q; j++)
{
if(A[j]<=x)
{
i=i+1;
swap(A[i],A[j]);
}
}
swap(A[i],A[p]);
return i;
}
Live example: ideone