/******************************************************************
This file is for the Sorting Competition project in the Algorithms
Course (COT4400). You need to implement a sorting procedure, called
"sort," and place it in the "sort.c" file.
******************************************************************/

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

// The declaration of the sorting procedure.
void sort(int* a, int n);

// The file with the sorting procedure.
#include "sort.c"

// The array size; that is, the procedure sorts an array a[0..SIZE-1].
#define SIZE 1000000

// The lower and upper bound on the values in the array; that
// is, every value in a[0..SIZE-1] is between MIN and MAX.
#define MIN -5000000
#define MAX 5000000

// The seed for the random-number generator.
#define SEED 0

// The number of calls to the sorting procedure; that is,
// call "sorting" that many times, with different arrays.
#define TESTS 10

// Random values used in generating a shuffled array
// and checking the correctness of sorting.
int x, y, z;

// Generate a random value between "lower" and "upper."
int randomize(int lower, int upper) {
	return (int)((float)rand() / RAND_MAX * (upper - lower)) + lower;}

// Randomly shuffle elements of the array a[0..n-1].
void shuffle(int* a, int n) {
	int i, j, key;
	for (j = n - 1; j > 0; j--) {
		i = randomize(0, j);
		key = a[i];
		a[i] = a[j];
		a[j] = key;}}

// Randomly fill the array a[0..n-1] with 
// values between "lower" and "upper."
void fill(int* a, int n, int lower, int upper) {
	int j;
	a[n / 4] = y = randomize(lower, upper);
	a[n / 2] = x = randomize(lower, y);
	a[3 * n / 4] = z = randomize(y, upper);
	for (j = 0; j < n / 4; j++) a[j] = randomize(lower, x);
	for (j = n / 4 + 1; j < n / 2; j++) a[j] = randomize(x, y);
	for (j = n / 2 + 1; j < 3 * n / 4; j++) a[j] = randomize(y, z);
	for (j = 3 * n / 4 + 1; j < n; j++) a[j] = randomize(z, upper);
	shuffle(a, n);}

// Check the correctness of sorting; note that it checks only three
// elements of the array, and may sometime accept an incorrectly
// sorted array as correct. 
int check(int* a, int n) {
	return a[n / 4] == x && a[n / 2] == y && a[3 * n / 4] == z;}

// Test the correctness of the sorting procedure, on several
// randomly generated arrays, and measure the sorting time.
int main(void) {
	int a[SIZE];
	int right = 0, test;
	clock_t timer = 0;
	srand(SEED);
	for (test = 0; test < TESTS; test++) {
		fill(a, SIZE, MIN, MAX);
		timer -= clock();
		sort(a, SIZE);
		timer += clock();
		if (check(a, SIZE)) right++;}
	if (right == TESTS) printf("Sorting is correct");
	else printf("%d out of %d arrays are correct", right, TESTS);
	printf("; mean sorting time is %.3f seconds\n",
	       (float)timer / CLOCKS_PER_SEC / TESTS);
	return 0;}