#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
/****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.
 ****/
#define	TEN	8
#define DEBUG 1
#define WRITELINE2  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");\
        }
#define CHECKLINE  for(i=0;i<n_t-1;i++) if (ptr[i]>ptr[i+1]) {printf("Not Sorted\n"); }
#define WRITELINE1   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");\
        }
#define WRITE1	elapsed=0.0; for(j=0;j<runs;j++){ for(i=0;i<n_t;i++) ptr[i] = bptr[i]; t0=clock();
#define WRITE2  t1=clock(); elapsed +=(t1-t0)/((double)CLOCKS_PER_SEC); }

extern clock_t clock();
void quick();
void quicker();
void merge();

int compare(const void *x,const void *y)
{
	return(* ((int*)x)-*((int*)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 runs \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)));
/*
   for(i=0;i<n_t;i++) bptr[i]=ptr[i]=n_t-i;
*/


/* generic qsort */
        WRITELINE1
        WRITE1;
        qsort(ptr,n_t,sizeof(int),compare); 
        WRITE2;
        WRITELINE2;
        CHECKLINE;
        printf("qsort      generic:Elapsed time is %10.8f\n",elapsed/runs);
        printf("*****\n");
/* recursive Shell Sort */
        WRITELINE1
        WRITE1;
	insertg(ptr,n_t,sizeof(int),compare); 
        WRITE2;
        WRITELINE2;
        CHECKLINE;
        printf("InsertionS generic:Elapsed time is %10.8f\n",elapsed/runs);
        printf("*****\n");

/* recursive Shell Sort Newer version?*/
        WRITELINE1
        WRITE1;
	quicker(ptr,n_t,sizeof(int),compare); 
        WRITE2;
        WRITELINE2;
        CHECKLINE;
        printf("NonRQuickS generic:Elapsed time is %10.8f\n",elapsed/runs);
        printf("*****\n");

/*           Heapsort (max heap)      */
        WRITELINE1
        WRITE1;
	fasterg(ptr,n_t,sizeof(int),compare); 
        WRITE2;
        WRITELINE2;
        CHECKLINE;
        printf("NonRQ2Quickgeneric:Elapsed time is %10.8f\n",elapsed/runs);
        printf("*****\n");

/*           Heapsort (min heap)     ?*/
        WRITELINE1
        WRITE1;
	mnheap(ptr,n_t,sizeof(int),compare); 
        WRITE2;
        WRITELINE2;
        CHECKLINE;
        printf("HeapSortMN generic:Elapsed time is %10.8f\n",elapsed/runs);
        printf("*****\n");

        WRITELINE1
        WRITE1;
	mxheap(ptr,n_t,sizeof(int),compare); 
        WRITE2;
        WRITELINE2;
        CHECKLINE;
        printf("HeapSortMX generic:Elapsed time is %10.8f\n",elapsed/runs);
        printf("*****\n");

        WRITELINE1
        WRITE1;
	merge(ptr,n_t,sizeof(int),compare); 
        WRITE2;
        WRITELINE2;
        CHECKLINE;
        printf("MergeSort  generic:Elapsed time is %10.8f\n",elapsed/runs);
        printf("*****\n");

}
