// straightforward (and inefficient) implementation of Quicksort, with a
// test 

#include <stdlib.h>
#include <string.h>

// qs() does Quicksort on the array of n integers pointed to by x
void qs(int *x, int n)

{  int pivot = x[0], // comparison element
       *p1,n1,  // pointer and length for first subarray
       *p2,n2,  // pointer and length for second subarray
       i,xi;
  
   if (n <= 1) return;
   p1 = malloc(n*sizeof(int));  n1 = 0;
   p2 = malloc(n*sizeof(int));  n2 = 0;
   // array separation
   for (i = 1; i < n; i++)  {
      xi = x[i];
      if (xi < pivot) 
         p1[n1++] = xi;
      else p2[n2++] = xi;
   }
   // recursive calls
   qs(p1,n1);
   qs(p2,n2);
   // bcopy() is a C library function; see man page
   bcopy(p1,x,n1*sizeof(int));
   x[n1] = pivot;
   bcopy(p2,x+n1+1,n2*sizeof(int));
}

// test code
main(int argc, char** argv)

{  int *p,nelts,i;

   // create a test array with random numbers from 0 to 99
   nelts = atoi(argv[1]);
   p = malloc(nelts*sizeof(int));
   for (i = 0; i < nelts; i++)
      p[i] = random() % 100;
   // try the sort
   qs(p,nelts);
   // print results
   for (i = 0; i < nelts; i++)
      printf("%d\n",p[i]);
}