#include <stdio.h>
#include <stdlib.h>    // for random number generators: srand() and rand()
#include <time.h>      // for time()
#include <string.h>    // for memcpy()

#define MAX_SIZE 2500  // size of input


void initArray(int array[], int range);
void copyArray(int destArray[], int srcArray[]);
int checkEqual(int arrayA[], int arrayB[]);
int compare(const void *p1, const void *p2);

void selectionsort(int array[]);
void mergesort(int array[]);
void countsort(int array[]);

int main()
{
	int array0[MAX_SIZE];
	int array1[MAX_SIZE];
	int array2[MAX_SIZE];
	int array3[MAX_SIZE];

	srand(time(NULL));  // initialize random number generator 

	// prepare input arrays
	// all four arrays have the same values in them
	initArray(array0, MAX_SIZE);
	copyArray(array1, array0); 
	copyArray(array2, array0); 
	copyArray(array3, array0); 

	// run sort algorithms
	qsort(array0, MAX_SIZE, sizeof(int), compare);
	selectionsort(array1);
	mergesort(array2);
	countsort(array3);

	// check correctness by comparing with result from qsort 
	if ( checkEqual(array0, array1) )
		printf("Selection sort is correct!\n");
	if ( checkEqual(array0, array2) )
		printf("Merge sort is correct!\n");
	if ( checkEqual(array0, array3) )
		printf("Count sort is correct!\n");

	return;
}

/************************************************************ 
 * Initialize array with random values between 0 ~ range-1.
 ***********************************************************/ 
void initArray(int array[], int range)
{
	int i;
	for( i = 0; i < MAX_SIZE; i++ )
	{
		array[i] = rand() % range;
	}
}

/************************************************************ 
 * Copy array from destArray to srcArray 
 ***********************************************************/ 
void copyArray(int destArray[], int srcArray[])
{
	memcpy(destArray, srcArray, MAX_SIZE*sizeof(int));
}

/************************************************************ 
 * Check if two arrays are equal
 ***********************************************************/ 
int checkEqual(int arrayA[], int arrayB[])
{
	int i;
	for (i = 0; i < MAX_SIZE; i++) 
		if( arrayA[i] != arrayB[i])
			return 0;
	return 1;
}

/************************************************************ 
 * Compare function for qsort 
 ***********************************************************/ 
int compare(const void *p1, const void *p2)
{
	int left = *((int*)p1);
	int right = *((int*)p2);
	if (left == right)
		return 0;
	else
		return ((left < right)?(-1):(1));
}

/************************************************************ 
 * Implement this function  
 ***********************************************************/ 
void selectionsort(int array[])
{
	return;
}

/************************************************************ 
 * Implement this function  
 ***********************************************************/ 
void mergesort(int array[])
{
	return;
}

/************************************************************ 
 * Implement this function  
 ***********************************************************/ 
void countsort(int array[])
{
	return;
}