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

/* An implementation of the quicksort algorithm for double precision
   arrays. */

/* Swap positions a and b in V. */
void swap(double* V,
          const int a,
          const int b)
{
  double U = V[a];
  V[a] = V[b];
  V[b] = U;
}


/* A crude quicksort algorithm.  The partition element should be
   chosen more intelligently. */
void quicksort(double* V,
               const int n)
{
  /* The partition element. */
  double X = V[0];

  /* The sentinels. */
  int i1 = 0, i2 = n, k;

  /* Break out of the recursion. */
  if (n < 2) return;

  /* Squeeze the sentinels together. */
  while (1)
    {
      /* Find the proper location for the left sentinel. */
      while ( (++i1 < n) && (V[i1] <= X) );
      
      /* Find the proper location for the right sentinel. */
      while ( (--i2 >= 0) && (V[i2] >= X) );

      /* We found a pair to interchange. */
      if (i1 < i2) swap(V, i1, i2);

      /* The sentinals crossed each other. */
      else
        {
          /* Recursive calls. */
          quicksort(V+1, i1-1);
          quicksort(V+i1, n-i1);
          
	  /* Put the partition element between the sorted sub-arrays. */
          for (k=0; k<i1-1; ++k) V[k] = V[k+1];
          V[i1-1] = X;
          return;
        }
    }
}


int main(int argc, 
         char** argv)
{
  double* V;
  int L, k;
  clock_t TI, TF;
  double TE;

  srand48(7348348);

  /* Check the command line arguments. */
  if (argc != 2)
    {
      printf("Usage: %s <length>\n", argv[0]);
      exit(0);
    }

  /* Construct a random array. */
  L = atoi(argv[1]);
  V = (double*)malloc(L*sizeof(double));
  for (k=0; k<L; ++k) V[k] = drand48();

  /* Print the sorted array. */
  /*for (k=0; k<L; ++k) printf("%f\n", V[k]);*/

  /* Get the initial CPU time. */
  TI = clock();

  /* Do the sort. */
  quicksort(V, L);

  /* Get the final CPU time. */
  TF = clock();
  
  /* Get the elapsed time. */
  TE = ((double)(TF - TI)) / CLOCKS_PER_SEC;
  printf("Size: %5d, Elapsed time: %12.4f\n\n", L, TE);

  /* Print the sorted array. */
  /*for (k=0; k<L; ++k) printf("%f\n", V[k]);*/

  return 0;
}