Problem with my quicksort implementation

Question

Newbie programmer here trying to implement quicksort, yet it won't work. I've looked at online resources but I just can't seem to spot the error in my implementation. Thanks in advance.

EDIT Issue I'm having seems like it gets stuck in the quicksort function, and the program just hangs. When I tried debugging it with printf's, the original array seems to have been modified with unexpected numbers (not from the original list), such as 0's.

void quicksort(int a[], const int start, const int end)
{
   if( (end - start + 1 ) < 2)
      return;

   int pivot = a[rand()%(end - start)];

   //Two pointers
   int L = start;
   int R = end;

   while(L < R)
   {
      while(a[L] < pivot)
         L++;
      while(a[R] > pivot)
         R--;
      if(L < R)
         swap(a,L,R);      
   }
   quicksort(a, start, L-1);
   quicksort(a, L+1, end );
}

void swap(int a[], const int pos1, const int pos2)
{
   a[pos1] ^= a[pos2];
   a[pos2] ^= a[pos1];
   a[pos1] ^= a[pos2];
}

int main()
{
   int array[20] = {0};
   int size = sizeof(array)/sizeof(array[0]);//index range = size - 1

   int i = 0;
   printf("Original: ");
   for (i; i < size; i++)
   {
      array[i] = rand()%100+ 1;
      printf("%d ", array[i]);
   }
   printf("\n");

   quicksort(array,0,size-1);

   int j = 0;
   printf("Sorted: ");
   for(j; j < size; j++)
      printf("%d ", array[j]);
   printf("\n");
}

Additional Question: In regards to calling quicksort recursively, would the left and right pointer always point towards the pivot at the end of each partition? If so, is calling quicksort from start to L-1 and L+1 to end correct?

Also, is the if (L < R) before the swap necessary?

What is the symptom? Current results vs. expected? Please don't just ask us to fix your big blob of code. — John Zwinck
Woops. It gets stuck somewhere; it won't exit out of quicksort. And when it somehow managed to exit, it introduced numbers that weren't in the original list. — ntan
Note that the xor trick fails if you try to swap an object with itself (not an issue in this case). — Keith Thompson

templatetypedef templatetypedef · Accepted Answer · 2011-08-25T01:36:51

I believe that the problems stem from two errors in the logic. The first one is here:

int pivot = a[rand()%(end - start)];

Note that this always picks a pivot in the range [0, end - start) instead of [start, end). I think you want to have something like

int pivot = a[rand()%(end - start) + start];

so that you pick a pivot in the range you want.

The other error is in this looping code:

while(L < R)
{
   while(a[L] < pivot)
      L++;
   while(a[R] > pivot)
      R--;
    if(L < R)
      swap(a,L,R);      
}

Suppose that L < R, but that a[L], a[R], and pivot are all the same value. This might come up, for example, if you were quicksorting a range containing duplicate elements. It also comes up when you use rand with the standard Linux implementation of rand (I tried this on my machine and 27 was duplicated twice). If this is the case, then you never move L or R, because the conditions in the loops always evaluate to false. You will need to update your logic for partitioning elements when duplicates are possible, since otherwise you'll go into an infinite loop here.

Hope this helps!

Problem with my quicksort implementation

2 Answers