#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#define	TEN	8
#define DEBUG 1
/****Copyright (c) 1997,1998,1999-2002 All rights reserved
 ****A. V. Gerbessiotis 
 ****Permission to use, copy, modify, and distribute this software,
 ****and to incorporate it, in whole or in part, into 
 ****other software,is hereby granted without fee, provided that
 ****  (1) the above copyright notice and this permission 
 ****      notice appear in all copies of the source code, and 
 ****      the above copyright notice appear in clearly visible 
 ****      form on all supporting documentation and distribution 
 ****      media, and
 ****     (2) any redistribution of the software, in original
 ****         or modified form, be without fee and subject to
 ****         these same conditions.
 ****   No guarantee, whatsoever, is offered that the code works as
 ****   advertised or is absent of any, even damaging,
 ****   side-effects. Use this code at your own personal risk.
 ****/

extern clock_t clock();
void quicki();
void quickeri();

int compare(int *x,int *y)
{
	return(*x-*y);
}


int main(int argc,char *argv[])
{
	int i,j,n,runs;
	int *ptr,*bptr;
	clock_t t1,t0;
	size_t n_t;
   	double elapsed;

	n=100;runs=1;
   if ( argc == 1 )
   	{
	      printf("Usage: sort size \n");
		n=100;
	}
   else
	   {
		n = atoi(argv[1]);
		runs=atoi(argv[2]);
	   }

	ptr= (int*) malloc(n*sizeof(int));
	bptr= (int*) malloc(n*sizeof(int));

	n_t =  n;

	for(i=0;i<n_t;i++) bptr[i]=ptr[i] = (int) (n_t*(random()/ ((double) INT_MAX)));


/* generic qsort */
/*
if (DEBUG) {
	for(i=0;i<TEN;i++) printf("%d ",ptr[i]); printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr[i]); printf("\n");
}
	elapsed=0.0; for(j=0;j<runs;j++){	
	for(i=0;i<n_t;i++) ptr[i] = bptr[i];
	t0=clock(); qsort(ptr,n_t,sizeof(int),compare); t1=clock();
	elapsed +=(t1-t0)/((double)CLOCKS_PER_SEC);
	}

if (DEBUG) {
	for(i=0;i<TEN;i++) printf("%d ",ptr[i]); printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr[i]); printf("\n");
}
        printf("qsort generic:Elapsed time is %10.8f\n",elapsed/runs);

*/
/* quicksort +str insertion */
	for(i=0;i<n_t;i++) ptr[i] = bptr[i];
if (DEBUG) {
	for(i=0;i<TEN;i++) printf("%d ",ptr[i]); printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr[i]); printf("\n");
}
	elapsed=0.0; for(j=0;j<runs;j++){	
	for(i=0;i<n_t;i++) ptr[i] = bptr[i];
	t0=clock(); quick2i(ptr,n_t); t1=clock();
	elapsed +=(t1-t0)/((double)CLOCKS_PER_SEC);
	}
if (DEBUG) {
	for(i=0;i<TEN;i++) printf("%d ",ptr[i]); printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr[i]); printf("\n");
}
        printf("quicksort+str insertion integer:Elapsed time is %10.8f\n",elapsed/runs);


/* quick sort non recursive generic */
	for(i=0;i<n_t;i++) ptr[i] = bptr[i];
if (DEBUG) {
	for(i=0;i<TEN;i++) printf("%d ",ptr[i]); printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr[i]); printf("\n");
}
	elapsed=0.0; for(j=0;j<runs;j++){	
	for(i=0;i<n_t;i++) ptr[i] = bptr[i];
	t0=clock(); quickeri(ptr,n_t); t1=clock();
	elapsed +=(t1-t0)/((double)CLOCKS_PER_SEC);
	}
if (DEBUG) {
	for(i=0;i<TEN;i++) printf("%d ",ptr[i]); printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr[i]); printf("\n");
}
        printf("quicksort non recursive integer:Elapsed time is %10.8f\n",elapsed/runs);


/* quick sort constantinos's version generic  */
	for(i=0;i<n_t;i++) ptr[i] = bptr[i];
if (DEBUG) {
	for(i=0;i<TEN;i++) printf("%d ",ptr[i]); printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr[i]); printf("\n");
}
	elapsed=0.0; for(j=0;j<runs;j++){	
	for(i=0;i<n_t;i++) ptr[i] = bptr[i];
	t0=clock(); quick3i(ptr,n_t,sizeof(int),compare); t1=clock();
	elapsed +=(t1-t0)/((double)CLOCKS_PER_SEC);
	}
if (DEBUG) {
	for(i=0;i<TEN;i++) printf("%d ",ptr[i]); printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr[i]); printf("\n");
}
        printf("quick3 (cosntantinos version) integer:Elapsed time is %10.8f\n",elapsed/runs);


/* quick sort gnu version generic  */
	for(i=0;i<n_t;i++) ptr[i] = bptr[i];
if (DEBUG) {
	for(i=0;i<TEN;i++) printf("%d ",ptr[i]); printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr[i]); printf("\n");
}
	elapsed=0.0; for(j=0;j<runs;j++){	
	for(i=0;i<n_t;i++) ptr[i] = bptr[i];
	t0=clock(); gnu_qsort(ptr,n_t,sizeof(int),compare); t1=clock();
	elapsed +=(t1-t0)/((double)CLOCKS_PER_SEC);
	}
if (DEBUG) {
	for(i=0;i<TEN;i++) printf("%d ",ptr[i]); printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr[i]); printf("\n");
}
        printf("gnusort version integer:Elapsed time is %10.8f\n",elapsed/runs);

	free((void *) ptr);
	free((void *) bptr);
}
