/* C, hand-coded quicksort */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

typedef TYPE T;

void mysort(T* data, int N)
{
  int i, j;
  T v, t;

  if(N<=1) return;

  // Partition elements
  v = data[0];
  i = 0;
  j = N;
  for(;;)
  {
    /*
      original code was
             while(data[++i] < v && i < N) { }
      but this reads off the end of the array;
      Francisco Rosales provided a corrected version:
    */
    while(i < N && data[++i] < v) { }
    while(data[--j] > v) { }
    if(i >= j) break;
    t = data[i]; data[i] = data[j]; data[j] = t;
  }
  t = data[i-1]; data[i-1] = data[0]; data[0] = t;
  mysort(data, i-1);
  mysort(data+i, N-i);
}

void test(int N)
{
  T* data;
  time_t begin, end;
  double time_elapsed;
  int i;

  if(N < 1)
  {
    printf("Input value %d too small.\n", N);
    return;
  }

  data = (T*) malloc(N*sizeof(T));
  if(!data)
  {
    printf("Could not allocate data - %d bytes.\n", N*sizeof(T));
    return;
  }
  for(i=0; i<N; ++i)
    data[i] = rand();

  begin = clock();
  mysort(data, N);
  end = clock();
  time_elapsed = (double)(end-begin)/CLOCKS_PER_SEC;

  printf("%7.2lf\n", time_elapsed);
  free(data);
}

int main(int argc, char* argv[])
{
  int i;
  if(argc != 2)
    printf("Usage: %s <array-size>\n", argv[0]);
  else
  {
    for(i=0; i<10; ++i)
      test(atoi(argv[1]));
  }
  return 0;
}