quicksort puzzle - (nf)

[utzoo!decvax!harpo!seismo!hao!hplabs!sri-unix!mclure]

#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);
    }
}