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

#define MAX 20000

static int N ;
static int a[MAX+1];

//================================= insertion sort ============================================
void insertion (int a[], int N)
{
	int i, j, v;

	for (i = 2; i <= N; i++)
	{
		v = a[i]; j = i;
		while (a[j-1] > v)
			{a[j] = a[j-1]; j--;}
		a[j] = v;
	}
}

//=============================== quicksort rekursiv =========================================
void quicksort (int a[], int l, int r)
{
	int v, i, j, t;

	if (r > l)
	{
		v = a[r]; i = l-1; j = r;
		for (;;)
		{
			while (a[++i] < v) ;
			while (a[--j] > v) ;
			if (i >= j) break;
			t = a[i]; a[i] = a[j]; a[j] = t;
		}
		t = a[i]; a[i] = a[r]; a[r] = t;
		quicksort (a, l, i-1);
		quicksort (a, i+1, r);
	}
}

//================================ shellsort ==============================================
void shellsort (int a[], int N)
{
	int i, j, h, v;

	for (h = 1; h <= N/3; h = 3*h + 1) ;
	for ( ; h > 0; h /= 3)
		for (i = h + 1; i <= N; i++)
		{
			v = a[i]; j = i;
			while (j > h && a[j-h] > v)
			{ a[j] = a[j-h]; j -= h;}
			a[j] = v;
		}
}

// =============================== Heapsort =============================================

void upheap (int k)
{
	int v;

	v = a[k]; a[0] = INT_MAX;
	while (a[k/2] <= v)
	{ a[k] = a[k/2]; k = k/2; }
	a[k] = v;
}

void insert (int v)
{
	a[++N] = v;
	upheap (N);
}

void downheap (int k)
{
	int j, v;

	v = a[k];
    while (k <= N/2)
	{
		j = k+k;
		if (j < N && a[j] < a[j+1]) j++;
		if (v >= a[j]) break;
		a[k] = a[j]; k = j;
	}
	a[k] = v;
}

int removes ()
{
	int v = a[1];

	a[1] = a[N--];
	downheap (1);
	return v;
}

void heapsort (int a[], int laenge)
{
	int k;

	for (k = 1; k <= laenge; k++) insert (a[k]);
	for (k = laenge; k >= 1; k--) a[k] = removes();
}



//===================================== Ende Sortierverfahren ==========================================

//array initaliesierung !
void initAufsteigend(int array[],int size)
{
	int index ;
	for (index = 1;index <= size;index++)
	{
		array[index] = index;
	}
}

void initAbsteigend(int array[],int size)
{
	int index ;
	int count = size;

	for (index = 1; index <= size;index++)
	{
		array[index] = count;
		count--;
	}
}

void initRandom(int array[],int size)
{
	int index ;

	// immer die gleichen zufallswerte
	srand(time(NULL));

	for (index = 1; index <= size;index++)
	{
		array[index] = rand();
	}
}
void ausgabe (int array[],int size)
{
	int index;

	for (index = 1;index <= size;index++)
		{
			printf("%i ",array[index]);
		}
	printf("\n");
}

void testSort()
{
	int index ;

	for (index = 1;index < MAX;index++)
	{
		if (!(a[index] <= a[index+1])){
			printf(" ============= ERROR SORT ============ ");
		}
	}
}
int main(void)
{


	//absteigende eigenschaften
	int absteigend[6];
	int durschnittAbsteigend = 0.0;

	//aufsteigende eigenschaften
	int aufsteigend[6];
	int durschnittAufsteigend = 0.0;

	//random eigenschaften
	int random[6];
	int durschnittRandom = 0.0;

	int index;
	int clocks;

	// ==================================== insertion sort testing =================

	for (index = 1 ;index <= 5 ;index++)
	{

		initAbsteigend(a,MAX);
		clocks = clock();
		insertion(a,MAX);
		absteigend[index] = clock() - clocks ;


		initAufsteigend(a,MAX);
		clocks = clock();
		insertion(a,MAX);
		aufsteigend[index] = clock() - clocks ;


		initRandom(a,MAX);
		clocks = clock();
		insertion(a,MAX);
		random[index] = clock() - clocks ;

	}

	for (index = 1;index <= 5;index++)
	{
		durschnittAbsteigend += absteigend[index] ;
		durschnittAufsteigend += aufsteigend[index];
		durschnittRandom += random[index];
	}

	printf("Insertion Sort\n");
	printf("Absteigende Sort. Durschnittszeit %d \n",durschnittAbsteigend/5);
	printf("Aufsteigende Sort. Durschnittszeit %d \n",durschnittAufsteigend/5);
	printf("Random Sort. Durschnittszeit %d \n",durschnittRandom/5);

	// =============================  quicksort testing =========================

	durschnittAbsteigend 	= 0.0;
	durschnittAufsteigend 	= 0.0;
	durschnittRandom 		= 0.0;

	for (index = 1 ;index <= 5 ;index++)
	{

		initAbsteigend(a,MAX);
		clocks = clock();
		//quicksort(a,1,MAX);
		absteigend[index] = clock() - clocks ;
		durschnittAufsteigend += clock() - clocks;

		initAufsteigend(a,MAX);
		clocks = clock();
		//quicksort(a,1,MAX);
		aufsteigend[index] = clock() - clocks ;

		initRandom(a,MAX);
		clocks = clock();
		quicksort(a,1,MAX);
		random[index] = clock() - clocks ;
	}


	for (index = 1;index <= 5;index++)
	{
		durschnittAbsteigend += absteigend[index] ;
	//	durschnittAufsteigend += aufsteigend[index];
		durschnittRandom += random[index];
	}

	printf("\nQuick Sort\n");
	printf("Absteigende Sort. Durschnittszeit %d \n",durschnittAbsteigend/5);
	printf("Aufsteigende Sort. Durschnittszeit %d \n",durschnittAufsteigend/5);
	printf("Random Sort. Durschnittszeit %d \n",durschnittRandom/5);

// ============================  ShellSort Testing ==========================================

	durschnittAbsteigend 	= 0.0;
	durschnittAufsteigend 	= 0.0;
	durschnittRandom 		= 0.0;


	for (index = 1 ;index <= 5 ;index++)
	{

		initAbsteigend(a,MAX);
		clocks = clock();
		shellsort(a,MAX);
		absteigend[index] = clock() - clocks;


		initAufsteigend(a,MAX);
		clocks = clock();
		shellsort(a,MAX);
		aufsteigend[index] = clock() - clocks;


		initRandom(a,MAX);
		clocks = clock();
		shellsort(a,MAX);
		random[index] = clock() - clocks;

	}

	for (index = 1;index <= 5;index++)
	{
		durschnittAbsteigend += absteigend[index] ;
		durschnittAufsteigend += aufsteigend[index];
		durschnittRandom += random[index];
	}

	printf("\n Shell Sort\n");
	printf("Absteigende Sort. Durschnittszeit %d \n",durschnittAbsteigend/5);
	printf("Aufsteigende Sort. Durschnittszeit %d \n",durschnittAufsteigend/5);
	printf("Random Sort. Durschnittszeit %d \n",durschnittRandom/5);

// ====================================== HeapSort Testing =============================

	durschnittAbsteigend 	= 0.0;
	durschnittAufsteigend 	= 0.0;
	durschnittRandom 		= 0.0;


	for (index = 1 ;index <= 5 ;index++)
	{
		N = 0;

		initAbsteigend(a,MAX);
		clocks = clock();
		heapsort(a,MAX);
		absteigend[index] = clock() - clocks;

		N = 0;
		initAufsteigend(a,MAX);
		clocks = clock();
		heapsort(a,MAX);
		aufsteigend[index] = clock() - clocks;

		N = 0;
		initRandom(a,MAX);
		clocks = clock();
		heapsort(a,MAX);
		random[index] = clock() - clocks;
		testSort();

	}

	for (index = 1;index <= 5;index++)
	{
		durschnittAbsteigend += absteigend[index] ;
		durschnittAufsteigend += aufsteigend[index];
		durschnittRandom += random[index];
	}

	printf("\nHeap Sort\n");
	printf("Absteigende Sort. Durschnittszeit %d \n",durschnittAbsteigend/5);
	printf("Aufsteigende Sort. Durschnittszeit %d \n",durschnittAufsteigend/5);
	printf("Random Sort. Durschnittszeit %d \n",durschnittRandom/5);

	getchar();
	//ende main
	return 0;
}