Quicksort implementation error

Question

I was trying to implement quicksort. But the control seems to be never exiting the quicksort function. Any help would be much appreciated.

A few pointers:

1. I am using the first element as the pivot. I know much better and efficient techniques exist to choose the pivot, but this is not about that.

2.The 'k' variable in the partition function is the pivot element.

As far as I know, the problem is with the partition function, since I have tried debugging it various times.

Also, this is not a Homework question. I was trying to implement the algorithm after having learnt it by myself.

#include<iostream>
using namespace std;

void swap(int *a,int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

void readarray( int a[],int n)
{
    cout<<"Enter elements for the array\n";
    for(int i=0;i<n;i++)
        cin>>a[i];
}

void printarray(int a[],int n)
{
    cout<<"Elements are as follows\n";
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";

    cout<<endl;
}


int partition(int low,int high,int a[])
{
    int i,j,k;
    i=low;
    j=high;
    k=low;

    while(i<=j)
    {
        while(a[i]<a[k])
            i++;

        while(a[j]>=a[k])
            j--;


        if(i<=j)
        {
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }

    if(i>j)
        swap(a[k],a[j]);

    return j;
}

void quicksort(int low,int high,int a[])
{
    int k;
    if(low<high)
    {
        k=partition(low,high,a);
        quicksort(low,k-1,a);
        quicksort(k+1,high,a);
    }
}

int main()
{
    int a[20];
    int n;
    cout<<"Enter the size of the array\n";
    cin>>n;
    readarray(a,n);
    cout<<"Before sorting\n";
    printarray(a,n);

    quicksort(0,n,a);

    cout<<"After sorting contents are\n";

    printarray(a,n);

    return 0;
}

In the main function I have tried using both the quicksort(0,n,a) and quicksort(0,n-1,a). Neither worked.

Answer 1

There is problem with your partition routine, see comments:

int partition( int low, int high,int a[]) {
   int i, j, k;
   i = low; 
   j = high;
   k = low;

  while ( i < j )
 {
  while( a[i] <= a[k] ) // Move i while item < kth element
   i++;
  while( a[j] > a[k] ) // Move j while item > kth element
   j--;
  if ( i < j )
   swap(&a[i],&a[j]); //Pass address of elements
 }

swap(&a[low],&a[j]); // j is final position for the kth element (viz.the pivot )

   return j;
}

Call quick sort routine using:

quicksort(0,n-1,a);