#define SIZE 10000000
#define NB_TESTS 4
#include <stdio.h>
#include <stdlib.h>
#include <sys/times.h>
#include <time.h>

void sort (int array[],int size);

main( )
{
  int i,t ;
  long duration[NB_TESTS];
  long duration_val;
  clock_t starttime,endtime ;
  int *array;

  for (t=0;t<NB_TESTS;t++)
  {
    starttime=clock();
    array=(int*)malloc(sizeof(int)*SIZE);
    for ( i = 0 ; i < SIZE ; i++ )
      array[i]=(i*7)%SIZE;
    sort(array,SIZE);
    free(array);
    endtime=clock();
    duration[t]=1000*((double)(endtime-starttime))/CLOCKS_PER_SEC;
    fprintf(stderr," %dms",duration[t]);
  }
  duration_val=duration[0];
  for (t=1;t<NB_TESTS;t++)
    if (duration_val>duration[t])
      duration_val=duration[t];
  printf("%d",duration_val);
}

static void quicksort ( int array[], int low, int high )
{
  int pos  ;
  if ( low < high )
  {
    int item, i, j, t ;
    item = array[low] ;
    i = low ;
    j = high ;
    while ( i < j )
    {
      while ( array[j] > item )
        j = j - 1 ;
      while ( array[i] <= item  &&  i < j )
        i = i + 1 ;
      if ( i < j )
      {
        t = array[i] ;
        array[i] = array[j] ;
        array[j] = t ;
      }
    }
    pos = j ;
    t = array[low] ;
    array[low] = array[pos] ;
    array[pos] = t ;


    quicksort ( array, pos + 1, high ) ;
    quicksort ( array, low, pos - 1 ) ;
  }
}

void sort (int array[],int size)
{
  quicksort ( array, 0, size-1 ) ;
}