#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXSIZE 1000
int A[MAXSIZE];

void quickSort ( int i , int j )
{
   int pivot;
   int leftArray[MAXSIZE], rightArray[MAXSIZE];
   int lsize, rsize;
   int k, idx;

   if (i == j) return;

   pivot = A[i];
   k = i; lsize = rsize = 0;

   /* Separate out the left and right parts */
   while (k < j) {
      ++k;
      if (A[k] < pivot) leftArray[lsize++] = A[k];
      else rightArray[rsize++] = A[k];
   }

   /* Copy back the left part, the pivot and the right part to the original array */
   k = i;
   for (idx=0; idx<lsize; ++idx) A[k++] = leftArray[idx];
   A[k++] = pivot;
   for (idx=0; idx<rsize; ++idx) A[k++] = rightArray[idx];

   if (lsize > 0) quickSort(i,i+lsize-1);  /* Recursive call on the left part */
   if (rsize > 0) quickSort(j-rsize+1,j);  /* Recursive call on the right part */
}

void printArray ( int s )
{
   int i;

   for (i=0; i<s; ++i) printf("%3d",A[i]);
   printf("\n");
}

int main ()
{
   int s, i;

   srand((unsigned int)time(NULL));
   printf("Array size : "); scanf("%d",&s);
   for (i=0; i<s; ++i) A[i] = 1 + rand() % 99;
   printf("Array before sorting : ");
   printArray(s);
   quickSort(0,s-1);
   printf("Array after sorting  : ");
   printArray(s);
}