/*-------------------------------------------------------------*/ /* Written by J. Katajainen and J. L. Träff */ /* February & March, 1997 */ /* */ /* Compiled at DIKU as follows: */ /* %gcc -O4 -o test ftestbed.c -lm */ /*-------------------------------------------------------------*/ /* At DIKU: */ #define random() CombTaus() #define srandom(s) setrangen2(s,s) #define frandom() frand() #define false 0 #define true 1 #define element float #include #include #include #include #include "random.c" #include "linearprobingsort.c" #include "linearprobingsort.in-place.c" #include "linearprobingsort.in-place.adaptive.c" #include "bucketsort.c" #include "quicksort.c" #include "heapsort.bottom-up.c" /* timers */ clock_t c_start, c_stop; static void generate(char type, element a[], int n, unsigned long seed) { int i,j; float s; switch (type) { case 'i': printf("Generating an increasing sequence of %d numbers ...\n",n); for (i=0; ia[i+1]) return false; break; } return true; } static void show(element a[], int n) { int i; for (i=0; i4) { fprintf(stderr,"Usage: %s [] []\n",argv[0]); fprintf(stderr," where is one of the following\n"); fprintf(stderr," 'u' uniformly distributed numbers (default)\n"); fprintf(stderr," 'n' normally distributed numbers\n"); fprintf(stderr," 'e' exponentially distributed numbers\n"); fprintf(stderr," 'i' increasing sequence of numbers\n"); fprintf(stderr," 'd' decreasing sequence of numbers\n"); fprintf(stderr," 'z' all zeros.\n"); exit(1); } else { n = atoi(argv[1]); if (argc>=3) type = argv[2][0]; else type = 'u'; if (argc==4) seed = atoi(argv[3]); else seed = 1; } a = (element *) malloc(n*sizeof(element)); u = 1.6*n; /* 2.4*n would be safe but more time-consuming */ b = (element *) malloc(u*sizeof(element)); c = (int *) malloc(n*sizeof(int)); d = (int *) malloc(n*sizeof(int)); /* Experiments */ printf("\nLINEAR PROBING SORT:\n"); generate(type,a,n,seed); c_start = clock(); linear_probing_sort(a,b,n,u); c_stop = clock(); if (!sorted(type,a,n)) printf("*** Sorting error ***\n"); printf("CPU time (ms): %ld\n",(c_stop-c_start)/1000); printf("\nIN-PLACE LINEAR PROBING SORT:\n"); generate(type,a,n,seed); c_start = clock(); in_place_linear_probing_sort(a,n); c_stop = clock(); if (!sorted(type,a,n)) printf("*** Sorting error ***\n"); printf("CPU time (ms): %ld\n",(c_stop-c_start)/1000); printf("\nADAPTIVE IN-PLACE LINEAR PROBING SORT:\n"); generate(type,a,n,seed); c_start = clock(); adaptive_in_place_linear_probing_sort(a,n); c_stop = clock(); if (!sorted(type,a,n)) printf("*** Sorting error ***\n"); printf("CPU time (ms): %ld\n",(c_stop-c_start)/1000); printf("\nBUCKETSORT:\n"); generate(type,a,n,seed); c_start = clock(); bucketsort(a,b,c,d,n); c_stop = clock(); if (!sorted(type,a,n)) printf("*** Sorting error ***\n"); printf("CPU time (ms): %ld\n",(c_stop-c_start)/1000); printf("\nQUICKSORT:\n"); generate(type,a,n,seed); c_start = clock(); quicksort(a,n); c_stop = clock(); if (!sorted(type,a,n)) printf("*** Sorting error ***\n"); printf("CPU time (ms): %ld\n",(c_stop-c_start)/1000); printf("\nBOTTOM-UP HEAPSORT:\n"); generate(type,a,n,seed); c_start = clock(); bottom_up_heapsort(a,n); c_stop = clock(); if (!sorted(type,a,n)) printf("*** Sorting error ***\n"); printf("CPU time (ms): %ld\n",(c_stop-c_start)/1000); }