mclure (03/09/83)
#N:sri-unix:12100003:000:3501 sri-unix!mclure Jan 27 23:05:00 1983 /*********************************************************************** * Here's a more complicated puzzle. The following program contains a bug * which causes it to incorrectly sort a large int array only once in a * while. The rest of the time it sorts perfectly. The algorithm is * quicksort with the addition of a cutoff value below which an insertion * sort is used. The quicksort uses sentinels at the ends of the array * and contains various other non-pointer-involving optimizations (for * those of you who hate puzzles related to pointers). * The main algorithm is as follows: * * fill main array with random numbers and copy it to backup array * for i = 1 to maximum cutoff (100) * cutoff = i * output cutoff value * sort array * output time required to sort * check whether it is sorted * copy backup array to main array * * The quicksort, partition, and insertion algorithms are by way * of Bentley [1983, Writing Efficient Programs] which were in * turn by way of Aho et al and were translated into C from Pascal. * * If you're on an 11, you'll probably need separate I/D. Reducing * the array size somewhat does not eliminate the bad behavior. * * Have fun! ***********************************************************************/ #include <stdio.h> #include <sys/types.h> #include <sys/times.h> #define MAXCUT 100 /* Max cutoff to use for insert */ #define NUMPTS 5000 /* Size of array to sort */ #define MAXINT 32767 /* Maximum integer */ #define MAXFINT 32767. /* MAXINT in float */ int cutoff; /* Cutoff value for insertion */ int x[NUMPTS + 2], y[NUMPTS + 2]; main () { register i; long t, tott; struct tms ibuf, /* For times(2), change as suitable */ obuf; time (&t); srand (getpid () + (int) ((t >> 16) + t)); genran (); printf ("Cutoff Time\n"); for (i = 1; i <= MAXCUT; i++) { if (i%5 != 0) continue; cutoff = i; printf ("%5d....", i); tott = 0l; times (&ibuf); sort (1, NUMPTS); times (&obuf); tott = obuf.tms_utime + obuf.tms_stime - ibuf.tms_utime - ibuf.tms_stime; printf ("%ld", tott); if (issort ()) putchar ('\n'); cpyran (); } } issort () { register i; for (i = 0; i <= NUMPTS; i++) if (x[i] > x[i + 1]) { printf ("\toops! x[%d](%d) > x[%d](%d)!\n", i, x[i], i + 1, x[i + 1]); return (0); } return (1); } cpyran () { register i; for (i = 0; i <= NUMPTS + 1; i++) x[i] = y[i]; x[0] = -2; x[NUMPTS + 1] = MAXINT; } genran () { register i; for (i = 1; i <= NUMPTS; i++) x[i] = y[i] = rand () - 1; x[0] = -2; x[NUMPTS + 1] = MAXINT; } sort (l, u) int l, u; { register i, j, v, temp; if (u - l <= cutoff) for (i = l + 1; i <= u; i++)/* use insertion */ { j = i; temp = x[i]; while (temp < x[j - 1]) { x[j] = x[j - 1]; j--; } x[j] = temp; } else /* use quicksort */ { i = l + ((u - l + 1) * ((float) rand () / MAXFINT)); temp = x[i]; x[i] = x[u]; x[u] = temp; v = x[u]; i = l; j = u; while (i <= j) { while (x[j] >= v) j--; while (x[i] < v) i++; if (i < j) { temp = x[i]; x[i++] = x[j]; x[j--] = temp; } } if (i == l) { temp = x[l]; x[l] = x[u]; x[u] = temp; i++; j++; } sort (l, i - 1); sort (j + 1, u); } }