Sorting (Quicksort) ,Partition

Question

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

   temp=*a;
   *a=*b;
   *b=temp;
}

void partition(int a[],int size)
{
   int *right,*left,pivot=a[0],temp;

   right=&a[size-1];
   left=&a[0];
   while(1)
   {
      while(*left<=pivot)
      {
         left+=1;
      }

      while(*right>pivot)
      {
         right-=1;
      }

      if(right<left)
      {
         swap(&a[0],right);
         break;
      }

      swap(right,left);
   }
}

Is this code right?The pivot is getting placed in the right position but at hackerrank they said the right portion should be sorted in ascending order and the left portion of the array should be sorted in descending array.

Answer 1

Your code is not right: it does not do a stable partition of the array.

Imagine your array is

100, 33, 333, 22, 222, 11

After the stable partitioning around the first element, it should become

33, 22, 11, 100, 333, 222
// 33, 22, and 11 in the same order as in the original array
// 333 and 222 in the same order as in the original array

But, instead, it becomes

22, 11, 33, 100, 222, 333

_{Note that this partition implementation is ok for a non-stable quick sort: the pivot element is in the final position, all elements to its left are smaller, and all elements to its right are larger.}

Answer 2

In Quicksort you don't really sort elements in each partition.

After you chose a pivot value and do the partitioning, all the elements to the left of the pivot are less than the pivot but in any order; all the elements greater than the pivot are to its right in any order; the pivot is in its final place.

So hackerrank is wrong or, more likely, you misinterpreted what they say.