ソート関数 使用例

/*		test1.c			sort subroutine test		*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "sort.h"

#define		LEN		7

long _idum_u0;

void usage(uchar *s);
double urnd0(void);

void usage(uchar *s)
{
	fprintf(stderr, "Usage : %s  type   case   n   < print-flag >\n", s);
	fprintf(stderr, "      type = 1 : quick sort\n");
	fprintf(stderr, "           = 2 : bubble sort\n");
	fprintf(stderr, "           = 3 : insert sort\n");
	fprintf(stderr, "           = 4 : selection sort\n");
	fprintf(stderr, "           = 5 : merge sort\n");
	fprintf(stderr, "           = 6 : heap sort\n");
	fprintf(stderr, "           = 7 : inverse mapping sort\n");
	fprintf(stderr, "           = 8 : distribution counting sort\n");
	fprintf(stderr, "           = 9 : indirect quick sort\n");
	fprintf(stderr, "           =10 : indirect distribution counting sort\n");
	fprintf(stderr, "      case = 1 : for int data\n");
	fprintf(stderr, "           = 2 : for double data\n");
	fprintf(stderr, "           = 3 : for character string data\n");
	fprintf(stderr, "        n      : number of data\n");
	fprintf(stderr, "   print-flag  : if print, any character input.\n");
	exit(0);
}

main(int argc, char *argv[])
{
	int *ai, *alasti, *pi, *qi, *tmpi, *tlasti, *jun, *jlast;
	double *ad, *alastd, *pd, *qd, *tmpd, *tlastd;
	uchar **ac, **alastc, **pc, **qc, **tmpc, **tlastc, *b, *c;
	int i, j, pflag, n, n1, type, data;
	long stime, ttime;

	if(argc < 4)	usage(argv[0]);
	type = atoi(argv[1]);
	data = atoi(argv[2]);
	n = atoi(argv[3]);
	if(n <= 1 || type < 1 || type > 10 || data < 1 || data > 3 ||
	   (data == 2 && (type == 7 || type == 10)) ||
	   (data == 3 && (type == 7 || type == 8 || type == 10)))
	{
		fprintf(stderr, "Error : illegal data input.\n");
		if(n <= 1)	fprintf(stderr, "       n=%d   (must be n > 1)\n", n);
		else
			fprintf(stderr, "     type=%d  case=%d  not exist.\n", type, data);
		exit(-1);
	}
	ai = (int *)malloc(sizeof(int) * n);
	ad = (double *)malloc(sizeof(double) * n);
	ac = salloc(n, LEN);
	tmpi = (int *)malloc(sizeof(int) * n);
	tmpd = (double *)malloc(sizeof(double) * n);
	tmpc = salloc(n, LEN);
	jun = (int *)malloc(sizeof(int) * n);
	if(  ai == NULL ||   ad == NULL ||   ac == NULL ||
	   tmpi == NULL || tmpd == NULL || tmpc == NULL || jun == NULL)
	{
			fprintf(stderr, "Error : out of memory\n");
			exit(-2);
	}

	pflag = (argc > 4);
	alasti = ai + n - 1;
	alastd = ad + n - 1;
	alastc = ac + n - 1;
	tlasti = tmpi + n - 1;
	tlastd = tmpd + n - 1;
	tlastc = tmpc + n - 1;
	jlast = jun + n - 1;

	_idum_u0 = 987612345L;

	pi = tmpi;
	while(pi <= tlasti)	*pi++ = 65 + (int)(urnd0() * 26.);

	pd = tmpd;
	while(pd <= tlastd)	*pd++ = urnd0();

	pc = tmpc;
	while(pc <= tlastc)
	{
		c = *pc + LEN;
		*c-- = '\0';
		while(c >= *pc)	*c-- = 65 + (int)(urnd0() * 26.);
		pc++;
	}

	ttime = 0;
	if(type < 9)
	{
		switch(data)
		{
		case 1: 
			pi = ai;
			qi = tmpi;
			while(pi <= alasti)	*pi++ = *qi++;
			break;
		case 2:
			pd = ad;
			qd = tmpd;
			while(pd <= alastd)	*pd++ = *qd++;
			break;
		case 3:
			pc = ac;
			qc = tmpc;
			while(pc <= alastc)
			{
				for(b = *qc, c = *pc, j = 0; j <= LEN; j++)	*c++ = *b++;
				pc++;
				qc++;
			}
			break;
		}
	}
	if(pflag)
	{
		fprintf(stderr, "*** data print out ***\n\n");
		switch(data)
		{
		case 1:
			pi = ai;
			do{	printf("%c", *pi++); } while(pi <= alasti);
			break;
		case 2:
			pd = ad;
			do{	printf("%7.4f ", *pd++); } while(pd <= alastd);
			break;
		case 3:
			pc = ac;
			do{	printf("%7s ", *pc++); } while(pc <= alastc);
			break;
		}
		putchar('\n');
	}

	switch(type)
	{
	printf("\n");
	case 1:
		printf("*** quick sort ***\n");
		stime = clock();
		switch(data)
		{
		case 1:		qsort_i(ai, n);		break;
		case 2:		qsort_d(ad, n);		break;
		case 3:		qsort_c(ac, n);		break;
		}
		ttime = (clock() - stime);
		break;
	case 2:
		printf("*** bubble sort ***\n");
		stime = clock();
		switch(data)
		{
		case 1:		bsort_i(ai, n);		break;
		case 2:		bsort_d(ad, n);		break;
		case 3:		bsort_c(ac, n);		break;
		}
		ttime = (clock() - stime);
		break;
	case 3:
		printf("*** insert sort ***\n");
		stime = clock();
		switch(data)
		{
		case 1:		inssort_i(ai, n);	break;
		case 2:		inssort_d(ad, n);	break;
		case 3:		inssort_c(ac, n);	break;
		}
		ttime = (clock() - stime);
		break;
	case 4:
		printf("*** selection sort ***\n");
		stime = clock();
		switch(data)
		{
		case 1:		ssort_i(ai, n);		break;
		case 2:		ssort_d(ad, n);		break;
		case 3:		ssort_c(ac, n);		break;
		}
		ttime = (clock() - stime);
		break;
	case 5:
		printf("*** merge sort ***\n");
		stime = clock();
		switch(data)
		{
		case 1:		msort_i(ai, n);			break;
		case 2:		msort_d(ad, n);			break;
		case 3:		msort_c(ac, n, LEN);	break;
		}
		ttime = (clock() - stime);
		break;
	case 6:
		printf("*** heap sort ***\n");
		stime = clock();
		switch(data)
		{
		case 1:		hsort_i(ai, n);		break;
		case 2:		hsort_d(ad, n);		break;
		case 3:		hsort_c(ac, n);		break;
		}
		ttime = (clock() - stime);
		break;
	case 7:
		printf("*** inverse mapping sort ***\n");
		stime = clock();
		if(data == 1)	mapsort(ai, n, 255, 0);
		ttime = (clock() - stime);
		break;
	case 8:
		printf("*** distribution counting sort ***\n");
		stime = clock();
		switch(data)
		{
		case 1:		distsort_i(ai, n, 255, 0);	break;
		case 2:		distsort_d(ad, n, 1., 0.);	break;
		}
		ttime = (clock() - stime);
		break;
	case 9:
		printf("*** indirect quick sort ***\n");
		stime = clock();
		switch(data)
		{
		case 1:		iqsort_i(tmpi, n, jun);	break;
		case 2:		iqsort_d(tmpd, n, jun);	break;
		case 3:		iqsort_c(tmpc, n, jun);	break;
		}
		ttime = (clock() - stime);
		break;
	case 10:
		printf("*** indirect distribution counting sort ***\n");
		stime = clock();
		if(data == 1)	idistsort(tmpi, n, 255, 0, jun);
		ttime = (clock() - stime);
		break;
	}
	if(pflag)
	{
		if(type < 9)
		{
			switch(data)
			{
			case 1:
				pi = ai;
				do{	printf("%c", *pi++); } while(pi <= alasti);
				break;
			case 2:
				pd = ad;
				do{	printf("%7.4f ", *pd++); } while(pd <= alastd);
				break;
			case 3:
				pc = ac;
				do{	printf("%7s ", *pc++); } while(pc <= alastc);
				break;
			}
		}
		else
		{
			pi = jun;
			switch(data)
			{
			case 1:
				do{	printf("%c", *(tmpi + *pi)); } while(++pi <= jlast);
				break;
			case 2:
				do{	printf("%7.4f ", *(tmpd + *pi)); } while(++pi <= jlast);
				break;
			case 3:
				do{	printf("%7s ", *(tmpc + *pi)); } while(++pi <= jlast);
				break;
			}
		}
		putchar('\n');
	}

	if(pflag && type < 9)
	{
		printf("\n*** inverse test ***\n");
		switch(data)
		{
		case 1:
			inv_i(ai, n);
			pi = ai;
			do{	printf("%c", *pi); } while(++pi <= alasti);
			break;
		case 2:
			inv_d(ad, n);
			pd = ad;
			do{	printf("%7.4f ", *pd); } while(++pd <= alastd);
			break;
		case 3:
			inv_c(ac, n);
			pc = ac;
			do{	printf("%7s ", *pc); } while(++pc <= alastc);
			break;
		}
		putchar('\n');
	}

	printf("time : %ld [sec]\n\n", ttime);
	return 1;
}

double urnd0(void)
{
	double d = 1. / 4294967296.;
	return (double)(_idum_u0 *= 69069L) * d + 0.5;
}