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

#define RMAX 1000
#define CLK_TCK 1000

int 	bubble_swap_count=0,	ins_swap_count=0,	sel_swap_count=0,	merge_swap_count=0;
int 	bubble_comp_count=0,	ins_comp_count=0,	sel_comp_count=0,	merge_comp_count=0;
double	bubble_time,			ins_time,			sel_time,			merge_time;
int		bubble_rev_dir=0,		ins_rev_dir=0,		sel_rev_dir=0,		merge_rev_dir=0;


/* fuelle array mit zufaelligen Werten (< RMAX) */
static void fill_array(int arr[], int n) {
	int i;
	for (i = 0; i < n; i++)
		arr[i] = rand() % RMAX;
}


/* tausche den Inhalt zweier Variablen */
static void swap(int *a, int *b) {
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

/* bubble-sort */
static void bubble_sort(int arr[], int length)
{
	int i, swapped;
	do
	{
		swapped = 0;
		if (bubble_rev_dir)
		{
			for (i = 1; i < length; i++)
			{
				bubble_comp_count++;
				if (arr[i - 1] < arr[i])
				{
					swap(&arr[i - 1], &arr[i]);
					bubble_swap_count++;
					swapped = 1;
				}
			}
		}
		else
		{
			for (i = 1; i < length; i++)
			{
				bubble_comp_count++;
				if (arr[i - 1] > arr[i])
				{
					swap(&arr[i - 1], &arr[i]);
					bubble_swap_count++;
					swapped = 1;
				}
			}
		}
	} while (swapped);
}



/* insertion-sort */
static void insertion_sort(int arr[], int length) {
	int i, j, key;
	if (ins_rev_dir)
		{
			for (i = 1; i < length; i++) {
				key = arr[i];
				j = i - 1;
				ins_comp_count++;
				while (j >= 0 && key > arr[j]) {
					ins_swap_count++;
					arr[j + 1] = arr[j];
					j--;
				}
				arr[j + 1] = key;
			}
		}
	else
		{
			for (i = 1; i < length; i++) {
				key = arr[i];
				j = i - 1;
				ins_comp_count++;
				while (j >= 0 && key < arr[j]) {
					ins_swap_count++;
					arr[j + 1] = arr[j];
					j--;
				}
				arr[j + 1] = key;
			}
		}
}

/* selection-sort */
static void selection_sort(int arr[], int length) {
	int i, j, min, max;
	if (sel_rev_dir)
	{
		for (i = 0; i < length - 1; i++) {
			max = i;
			for (j = i + 1; j < length; j++)
				{
				sel_comp_count++;
				if (arr[j] > arr[max])
					max = j;
				}
			swap(&arr[i], &arr[max]);
			sel_swap_count++;
		}
	}
	else
	{
		for (i = 0; i < length - 1; i++) {
			min = i;
			for (j = i + 1; j < length; j++)
				{
				sel_comp_count++;
				if (arr[j] < arr[min])
					min = j;
				}
			swap(&arr[i], &arr[min]);
			sel_swap_count++;
		}
	}
}

/* Fuege (merge) zwei sortierte Partitionen zusammen */
static void merge(int arr[], int l, int m, int r) {
	int *tmp = (int *) malloc(sizeof(int) * (m - l + 1));
	int i, j = 0, k = m + 1;
	/* kopiere arr[l..m] in ein temporaeres Array */
	for (i = l; i <= m; i++)
		tmp[j++] = arr[i];
	/* vergleiche die Eintraege des temp. Arrays mit den Eintraegen arr[m+1..r] */
	i = l;
	j = 0;
	while (i < k && k <= r)
		{
		merge_comp_count++;
		if (tmp[j] <= arr[k])
			{
				arr[i++] = tmp[j++];
				merge_swap_count++;
			}
		else
			{
				arr[i++] = arr[k++];
				merge_swap_count++;
			}
		}
	/* kopiere eventuelle vorhandene Eintraege des temp. Arrays nach arr */
	while (i < k)
		{
			arr[i++] = tmp[j++];
			merge_swap_count++;
		}
	free(tmp);
}

/* merge-sort */
static void merge_sorter(int arr[], int l, int r) {
	int m = (l + r) / 2;
	/* arr[l..r] hat min. zwei Elemente <=> l < r */
	if (l < r) {
		/* sortiere ersten Teil */
		merge_sorter(arr, l, m);
		/* sortiere zweiten Teil */
		merge_sorter(arr, m + 1, r);
		/* Fuege sortierte Teile zusammen */
		merge(arr, l, m, r);
	}
}
/* Wrapper für mergesorter */
static void merge_sort(int arr[], int n) {
	merge_sorter(arr, 0, n - 1);
}


static double BeginTimer()
{
    //timer declaration
    clock_t Begin; //initialize Begin

    Begin = clock() * CLK_TCK; //start the timer

    return Begin;
}

static double EndTimer(clock_t begin)
{
    clock_t End;
    End = clock() * CLK_TCK;   //stop the timer

    return End;
}



static void any_key_wait()
{
	char cc;
	printf("\n ...Press Any Key To Exit... \n");
	do
		{
			//cc = getch();
		}
	while(!cc);
}


static void print_array(int arr[], int size)
{
	printf("\nSorted array:\n");
	for(int i=0;i<size;i++)
		printf("%d\t",arr[i]);
}


/* ueberpruefe, ob ein Array sortiert ist (zum Debuggen) */
static void check_sort(int arr[], int n, int DESC) {
	int i;
	for (i = 1; i < n; i++)

	if (DESC)
		{
			if (arr[i - 1] < arr[i]) {
			fprintf(stderr, "internal sort algorithm error\n");
			exit(EXIT_FAILURE);
			}
		}
	else
		{
			if (arr[i - 1] > arr[i]) {
			fprintf(stderr, "internal sort algorithm error\n");
			exit(EXIT_FAILURE);
			}
		}
}


static void usage_and_exit(char *prgname) {
	printf("usage: %s (bubble|insertion|merge|selection) SIZE [desc] [print]\n", prgname);
	printf("---------\n-Ascending sort is default sort order, add 'desc' parameter if you\nwant descending order.\n");
	printf("-If you want to print sorted array add 'print' parameter. Not recommended\n for large arrays\n");
	exit(EXIT_FAILURE);
}

int main(int argc, char **argv) {
	int *arr, n, DESC=0, print_arr=0;
	char *sort_name;
	int swap_counts;

	if (argc < 3)
	{
		 usage_and_exit(*argv);
	}

	if(argc == 4)
	{
		if(strcmp(argv[3], "desc") == 0)
			DESC = 1;
		else if(strcmp(argv[3], "print") == 0)
			print_arr = 1;
		else
			usage_and_exit(*argv);
	}


	if(argc >= 5)
	{
		if(strcmp(argv[4], "print") == 0)
			print_arr = 1;
		else
			usage_and_exit(*argv);
	}


	srand((unsigned) time(NULL));

	n = atoi(argv[2]);
	if (n <= 0) {
		printf("SIZE has to be a positive number\n");
		return EXIT_FAILURE;
	}


	arr = calloc(n, sizeof(int));
	fill_array(arr, n);

	printf("Start sorting ...\n");

	double begin = BeginTimer();
    //printf ("Timer set to: %.2f\n", begin); // print the initialised timer (0)

	if (!strncmp(argv[1], "merge", 5))
		{
			if (DESC) merge_rev_dir = 1;
			merge_sort(arr, n);
			sort_name = "Merge";
			swap_counts = merge_swap_count;
			printf("Sorting using merge sort method!\n");
		}
	else if (!strncmp(argv[1], "bubble", 6))
		{
			if (DESC) bubble_rev_dir = 1;
			bubble_sort(arr, n);
			sort_name = "Bubble";
			swap_counts = bubble_swap_count;
			printf("Sorting using bubble sort method!\n");
		}
	else if (!strncmp(argv[1], "insertion", 9))
		{
			if (DESC) ins_rev_dir = 1;
			insertion_sort(arr, n);
			sort_name = "Insertion";
			swap_counts = ins_swap_count;
			printf("Sorting using insertion sort method!\n");
		}
	else if (!strncmp(argv[1], "selection", 9))
		{
			if (DESC) sel_rev_dir = 1;
			selection_sort(arr, n);
			sort_name = "Selection";
			swap_counts = sel_swap_count;
			printf("Sorting using selection sort method!\n");
		}
	else
		usage_and_exit(*argv);

	printf("Sorting finished!\n");

	printf("%s sort made %i swaps\n",sort_name,swap_counts);


	// variable declarations used for time calculation
    float elapTicks;
    float elapMilli, elapSeconds, elapMinutes;

    // variable definitions on to calculate time taken
    elapTicks = EndTimer(begin);    // stop the timer, and calculete the time taken
    elapMilli = elapTicks/1000;     // milliseconds from Begin to End
    elapSeconds = elapMilli/1000;   // seconds from Begin to End
    elapMinutes = elapSeconds/60;   // minutes from Begin to End

    //printf ("Seconds passed: %.4f\n", elapSeconds);
	printf ("Milliseconds passed: %.2f\n", elapMilli);

	// Ueberpruefe, ob Array sortiert ist
	check_sort(arr, n, DESC);

	if (print_arr) print_array(arr, n);

	free(arr);

	// hold the window open
    //any_key_wait();

	return 0;

}