/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

/* sort.cpp -- test and time sorting algorithms
	Input lines:  algnum n mod
	Output lines: algnum n mod clicks nanosecs_per_elem
   This is predominantly a C program; the only use of C++
   sort function immediately below the include line.
 */

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

// To change from C++ back to C, remove the following two lines
// and the call to sort in main
#include <algorithm>
using namespace std;

/* Data and supporting functions */

#define MAXN 10000000

typedef int DType;

DType realx[MAXN];
int *x = realx;	/* allow x to shift for heaps */
int n;

void swap(int i, int j)
{	DType t = x[i];
	x[i] = x[j];
	x[j] = t;
}

int randint(int l, int u)
{	return l + (RAND_MAX*rand() + rand()) % (u-l+1);
}

/* LIBRARY QSORT */

int intcomp(int *x, int *y)
{	return *x - *y;
}

/* INSERTION SORTS */

/* Simplest insertion sort */
void isort1()
{	int i, j;
	for (i = 1; i < n; i++)
		for (j = i; j > 0 && x[j-1] > x[j]; j--)
			swap(j-1, j);
}

/* Write swap function inline */
void isort2()
{	int i, j;
	DType t;
	for (i = 1; i < n; i++)
		for (j = i; j > 0 && x[j-1] > x[j]; j--) {
			t = x[j];
			x[j] = x[j-1];
			x[j-1] = t;
		}
}

/* Move assignments to and from t out of loop */
void isort3()
{	int i, j;
	DType t;
	for (i = 1; i < n; i++) {
		t = x[i];
		for (j = i; j > 0 && x[j-1] > t; j--)
			x[j] = x[j-1];
		x[j] = t;
	}
}

/* QUICKSORTS */

/* Simplest version, Lomuto partitioning */
void qsort1(int l, int u)
{	int i, m;
	if (l >= u)
		return;
	m = l;
	for (i = l+1; i <= u; i++)
		if (x[i] < x[l])
			swap(++m, i);
	swap(l, m);
	qsort1(l, m-1);
	qsort1(m+1, u);
}

/* Sedgewick's version of Lomuto, with sentinel */
void qsort2(int l, int u)
{	int i, m;
	if (l >= u)
		return;
	m = i = u+1;
	do {
		do i--; while (x[i] < x[l]);
		swap(--m, i);
	} while (i > l);
	qsort2(l, m-1);
	qsort2(m+1, u);
}

/* Two-way partitioning */
void qsort3(int l, int u)
{	int i, j;
	DType t;
	if (l >= u)
		return;
	t = x[l];
	i = l;
	j = u+1;
	for (;;) {
		do i++; while (i <= u && x[i] < t);
		do j--; while (x[j] > t);
		if (i > j)
			break;
		swap(i, j);
	}
	swap(l, j);
	qsort3(l, j-1);
	qsort3(j+1, u);
}

/* qsort3 + randomization + isort small subarrays + swap inline */
int cutoff = 50;
void qsort4(int l, int u)
{	int i, j;
	DType t, temp;
	if (u - l < cutoff)
		return;
	swap(l, randint(l, u));
	t = x[l];
	i = l;
	j = u+1;
	for (;;) {
		do i++; while (i <= u && x[i] < t);
		do j--; while (x[j] > t);
		if (i > j)
			break;
		temp = x[i]; x[i] = x[j]; x[j] = temp;
	}
	swap(l, j);
	qsort4(l, j-1);
	qsort4(j+1, u);
}

/* selection */

void select1(int l, int u, int k)
{	int i, j;
	DType t, temp;
	if (l >= u)
		return;
	swap(l, randint(l, u));
	t = x[l];
	i = l;
	j = u+1;
	for (;;) {
		do i++; while (i <= u && x[i] < t);
		do j--; while (x[j] > t);
		if (i > j)
			break;
		temp = x[i]; x[i] = x[j]; x[j] = temp;
	}
	swap(l, j);
	if (j < k)
		select1(j+1, u, k);
	else if (j > k)
		select1(l, j-1, k);
}

/* HEAP SORTS */

void siftup(int u)
{	int i, p;
	i = u;
	for (;;) {
		if (i == 1)
			break;
		p = i / 2;
		if (x[p] >= x[i])
			break;
		swap(p, i);
		i = p;
	}
}

void siftdown1(int l, int u)
{	int i, c;
	i = l;
	for (;;) {
		c = 2*i;
		if (c > u)
			break;
		if (c+1 <= u && x[c+1] > x[c])
			c++;
		if (x[i] > x[c])
			break;
		swap(i, c);
		i = c;
	}
}

void siftdown1b(int l, int u) /* More C-ish version of 1 */
{	int i, c;
	for (i = l; (c = 2*i) <= u; i = c) {
		if (c+1 <= u && x[c+1] > x[c])
			c++;
		if (x[i] > x[c])
			break;
		swap(i, c);
	}
}

void hsort1()
{	int i;
	x--;
	for (i = 2; i <= n; i++)
		siftup(i);
	for (i = n; i >= 2; i--) {
		swap(1, i);
		siftdown1(1, i-1);
	}
	x++;
}

void hsort2()
{	int i;
	x--;
	for (i = n/2; i >= 1; i--)
		siftdown1(i, n);
	for (i = n; i >= 2; i--) {
		swap(1, i);
		siftdown1(1, i-1);
	}
	x++;
}

void siftdown3(int l, int u) /* push to bottom, then back up */
{	int i, c, p;
	i = l;
	for (;;) {
		c = 2*i;
		if (c > u)
			break;
		if (c+1 <= u && x[c+1] > x[c])
			c++;
		swap(i, c);
		i = c;
	}
	for (;;) {
		p = i/2;
		if (p < l)
			break;
		if (x[p] > x[i])
			break;
		swap(p, i);
		i = p;
	}
}

void hsort3()
{	int i;
	x--;
	for (i = n/2; i >= 1; i--)
		siftdown3(i, n);
	for (i = n; i >= 2; i--) {
		swap(1, i);
		siftdown3(1, i-1);
	}
	x++;
}

void siftdown4(int l, int u) /* replace swap with assignments */
{	int i, c, p;
	DType t;
	t = x[l];
	i = l;
	for (;;) {
		c = 2*i;
		if (c > u)
			break;
		if (c+1 <= u && x[c+1] > x[c])
			c++;
		x[i] = x[c];
		i = c;
	}
	x[i] = t;
	for (;;) {
		p = i/2;
		if (p < l)
			break;
		if (x[p] > x[i])
			break;
		swap(p, i);
		i = p;
	}
}

void hsort4()
{	int i;
	x--;
	for (i = n/2; i >= 1; i--)
		siftdown4(i, n);
	for (i = n; i >= 2; i--) {
		swap(1, i);
		siftdown4(1, i-1);
	}
	x++;
}


/* Other Sorts -- Exercises in Column 11 */

void selsort()  /* Selection sort */
{	int i, j;
	for (i = 0; i < n-1; i++)
		for (j = i; j < n; j++)
			if (x[j] < x[i])
				swap(i, j);
}

void shellsort()
{	int i, j, h;
	for (h = 1; h < n; h = 3*h + 1)
		;
	for (;;) {
		h /= 3;
		if (h < 1) break;
		for (i = h; i < n; i++) {
			for (j = i; j >= h; j -= h) {
				if (x[j-h] < x[j]) break;
				swap(j-h, j);
			}
		}
	}
}



/* SCAFFOLDING */

/* Timing */

void timedriver()
{	int i, k, algnum, mod, start, clicks;
	while (scanf("%d %d %d", &algnum, &n, &mod) != EOF) {
		if (mod <= 0)
			mod = 10*n;
		for (i = 0; i < n; i++)
			x[i] = randint(0, mod-1);
		k = n/2;
		start = clock();
		switch (algnum) {
		case 11: qsort(x, n, sizeof(int), (int (__cdecl *)(const void *,const void *)) intcomp); break;
		case 12: sort(x, x+n); break;
		case 21: isort1(); break;
		case 22: isort2(); break;
		case 23: isort3(); break;
		case 31: qsort1(0, n-1); break;
		case 32: qsort2(0, n-1); break;
		case 33: qsort3(0, n-1); break;
		case 34: qsort4(0, n-1); isort3(); break;
		case 41: select1(0, n-1, k); break;
		case 51: hsort1(); break;
		case 52: hsort2(); break;
		case 53: hsort3(); break;
		case 54: hsort4(); break;
		case 61: selsort(); break;
		case 62: shellsort(); break;
		}
		clicks = clock() - start;
		if (algnum == 41) { /* Test selection */
			for (i = 0; i < k; i++)
				if (x[i] > x[k])
					printf("  SELECT BUG i=%d\n", i);
			for (i = k+1; i < n; i++)
				if (x[i] < x[k])
					printf("  SELECT BUG i=%d\n", i);
		} else { /* Test sort */
			for (i = 0; i < n-1; i++)
				if (x[i] > x[i+1])
					printf("  SORT BUG i=%d\n", i);
		}
		printf("%d\t%d\t%d\t%d\t%g\n",
			algnum, n, mod, clicks,
			1e9*clicks/((float) CLOCKS_PER_SEC*n));
	}
}

/* Main */

int main()
{	timedriver();
	return 0;
}