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
#include
using namespace std;
void quickSort(vector
int partition(vector
int main()
{
vector
int p=0;
int q=10;
cout<<"======Original======="<
{
int r;
if(p
{
int x= A[p];
int i=p;
int j;
for(j=p+1; j
void q_sort(T input[], int l_idx, int r_idx, compare comp = compare()) {
if (l_idx >= r_idx)
return;
// The below is the partition block (can be made a sub function)
int left = l_idx;
int right = r_idx;
{
int pivot_idx = l_idx;
T pivot = input[pivot_idx];
while (left < right) {
while (comp(input[left], pivot))
left++;
while (comp(pivot, input[right]))
right--;
swap(input[left], input[right]);
}
swap(pivot, input[left]);
}
q_sort(input, l_idx, left, comp);
q_sort(input, left+1, r_idx, comp);
}
template
void quick_sort(T array[], int N, compare comp = compare()) {
// This is an improvisation on the merge sort algorithm
// is in-place and works on the divide-and-conquer methodology
// Choose a pivot and find its appropriate place, such that
// All elements less than the pivot are on its left and all elements
// greater are on its right. Once found, split the porlblem into subsets
// of elements less than and greater than the pivot and recursively
// follow the process.
q_sort(array, 0, N-1, comp);
}
int main()
{
int input[] = {11, 6, 3, 21, 9, 12};
std::cout << "Before : ";
for (int i=0; i < 6; i++)
std::cout << input[i] << " ";
std::cout << std::endl;
quick_sort(input, 6);
// or
//quick_sort(input, 6, std::greater
std::cout << "After : "; for (int i=0; i < 6; i++) std::cout << input[i] << " "; std::cout << std::endl; }