/* T02n04.c -- A moldy oldie!  This is my original version of T02n03.java,
 *   written many years ago in C.  Eventually, I plan to convert this to
 *   use doubles instead of ints, to match T02n03.java.  Eventually.
 *   No, it wouldn't take long, but I have other priorities.
 *   The only reason it is here at all is to serve as a demo for gprof.
 *
 * To compile and run for profiling with gprof:
 *   $ gcc -pg T02n04.c   (can use g++ instead)
 *   $ a.out <size>       (produces the file gmon.out)
 *   $ gprof
 */

#include <stdio.h>
#include <stdlib.h>

#define LARGEINT 10000
#define SMALLINT -9999

void create_list(int list[], int size)
{
        int i;

        for (i=0; i<size; i++) {
                list[i] = rand() % size;
        }
}

void minmax1(int list[], int n, int *minptr, int *maxptr)
{
	int i;

	*minptr = *maxptr = list[0];

	for (i=1; i<n; i++) {
		if (list[i] < *minptr)
			*minptr = list[i];
		if (list[i] > *maxptr)
			*maxptr = list[i];
	}
}

void minmax2(int list[], int n, int *minptr, int *maxptr)
{
	int *candidates;
	int i, j, k, low, high;

	if ((candidates = (int *) malloc ((n+1) * sizeof(int))) == NULL) {
		fprintf(stderr,"FATAL ERROR: malloc failed in minmax2.\n\n");
		exit(1);
	}

	low = 0;
	high = n;

	for (i=0;i<n-1;i+=2) {
		if (list[i] < list[i+1]) {
			candidates[low++] = list[i];
			candidates[high--] = list[i+1];
		} else {
			candidates[low++] = list[i+1];
			candidates[high--] = list[i];
		}
	}

		/* If there are an odd # of list items, the last item needs
		 * to be considered as both a min and a max candidate.
		 */

	if (i==n-1) {
		candidates[low++] = list[i];
		candidates[high--] = list[i];
	}

		/* Now just do the normal min search on the lower half
		 * and the max search on the upper half.
		 */

	*minptr = candidates[0];

	for (j=1; j<low; j++)
		if (candidates[j] < *minptr)
			*minptr = candidates[j];

	*maxptr = candidates[high+1];

	for (k=high+1; k<n+1; k++)
		if (candidates[k] > *maxptr)
			*maxptr = candidates[k];
}

void minmax3(int list[], int n, int *minptr, int *maxptr)
{
	int i;

	*minptr = *maxptr = list[0];

	for (i=1;i<n-1;i+=2) {
		if (list[i] < list[i+1]) {
			if (list[i] < *minptr)
				*minptr = list[i];
			if (list[i+1] > *maxptr)
				*maxptr = list[i+1];
		} else {
			if (list[i+1] < *minptr)
				*minptr = list[i+1];
			if (list[i] > *maxptr)
				*maxptr = list[i];
		}
	}

		/* If there's an extra, un-paired item left, it might
		 * be the new min or the new max.
		 */

	if (i==n-1) {
		if (list[i] < *minptr)
			*minptr = list[i];
		if (list[i] > *maxptr)
			*maxptr = list[i];
	}
}

int main (int argc, char *argv[])
{
	int *list;
	int listsize;
	int min1, min2, min3, max1, max2, max3;

	if (argc < 2) {
		printf("Enter the list size: ");
		scanf("%d",&listsize);
	} else {
		listsize = atoi(argv[1]);
	}

	if ((list = (int *) malloc (listsize * sizeof(int))) == NULL) {
		fprintf(stderr,"FATAL ERROR: malloc failed in main.\n\n");
		exit(1);
	}

	create_list(list,listsize);
	minmax1(list,listsize,&min1,&max1);
	minmax2(list,listsize,&min2,&max2);
	minmax3(list,listsize,&min3,&max3);

	printf("min1 = %d, max1 = %d\n",min1,max1);
	printf("min2 = %d, max2 = %d\n",min2,max2);
	printf("min3 = %d, max3 = %d\n",min3,max3);

	return 0;
}