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


int *A;
int length;
int i,j, choice,userchoice;
int k;

void lengthDefine ();/*defines the length of the array to be sorted*/
void initialize();/* defines the entries of the array to be sorted*/
void sortDefine();/*defines the sorting algorithm to be applied and applies it*/

void swap(int *, int *); /*exchange algorithm*/

void SS(int P[],int);    /*the Selection Sort algorithm.*/

int part (int P[], int, int, int);/*partition algorithm*/

void QSL (int P[], int, int);/*Quick Sort, last entry defines partition*/

void QSR  (int P[], int, int, int);/*Quick Sort, random entry defines partition*/

void mergeSort(int *array,int left, int right);
void merge(int *array, int left, int middle, int right);

void sort(int arr[], int beg, int end,int p);


void main()
{

	printf("Press 1 to begin a new test.\n");
	printf("Press 2 to exit.\n");
	scanf("%d",&choice);
	if (choice==2)
		exit(1);
	else if(choice==1)
	{
		lengthDefine ();//orizo to mikos tou pinaka
		initialize();//orizo ta stoixeia tou pinaka
		sortDefine();
		for (i=0;i<length;i++)
		{
			printf("%d\n", A[i]);
		}
		main();
	}
	else
	{
		printf("***Please choose from the numbers above!***\n");
		main();
	}
}






void lengthDefine ()
{
	printf("Choose the length of the array to be sorted. \n");
	scanf("%d",&length);
	A = (int*)calloc(length,sizeof(int));
	if (A==NULL)
	{
		printf("***Not enough memory!***\n");
		exit(1);
	}
}


void initialize()
{
	printf("Choose the method of initialisation: \n");
	printf("Press 1 for random initialisation. \n");
	printf("Press 2 for an 'almost sorted' initialisation\n");
	printf("Press 3 for manual initialisation\n");
	scanf("%d",&choice);




	switch(choice)
	{

		case 1:
		{

			for (i=0; i<length ; i++)
				A[i] = (int)rand();
			for (k=0;k<length;k++)
				printf("%d  ",A[k]);
			printf("\n");
		}
		break;
		case 2:
		{
			int max;
			int a;
			A[0]=10;
			max=A[0];
			for (i=0;i<length-1;i++)
			{
				if ((float)rand()/RAND_MAX<=0.9)
				{
					A[i+1]=max+1;
					max=A[i+1];
				}
				else
				{
					int a;
					a=(10*rand()/RAND_MAX);
					A[i+1]=max-a;
				}
			}

		}
		break;

		case 3:
		{
			for (i=0;i<length;i++)
			{
				printf("Please enter an integer number\n");
				scanf("%d",&A[i]);
			}
		}
		break;
		default:
		{
			printf("***Please choose from the numbers above!***\n");
			initialize ();
		}
	}
}


void sortDefine()
{
	printf("Choose the sorting algorithm you wish to apply: \n");
	printf("Press 1 for Selection Sort. \n");
	printf("Press 2 for Quick Sort (last entry defines particion).\n");
	printf("Press 3 for Quick Sort (random entry defines particion).\n");
	printf("Press 4 for Merge Sort.\n");
	printf("Press 5 to go back to the main menu.\n");
	scanf("%d",&choice);

	switch(choice)
	{
		case 1:
			SS (A,length);
		break;
		case 2:
		{

			QSL(A , 0, length-1);
		}
		break;
		case 3:
		{
			printf("Give the pivot between 0 and %d\n", length);
			do{
				scanf("%d", &userchoice);
				if((userchoice>=0) && (userchoice<=length)){
					printf("wrong data\n");
				}
			}while( (userchoice<=0) && (userchoice>=length));
			int p= userchoice;



			sort(A , 0, length-1, p);

		}
		break;
		case 4:
		{
			mergeSort(A,0, length);

		}
		break;
		case 5:
		{
			exit(1);
		}
		break;
	}
}

void SS(int P[],int l)
{
	int pos_min;

	for (i=0;i<l;i++)
	{
		pos_min=i;
		for (j=i;j<l;j++)
		{
			if (P[j]<P[pos_min])
				pos_min=j;
		}
		swap (&P[i],&P[pos_min]);
	}
}

void swap (int *a,int *b)
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

int part(int P[], int min_p , int max_p, int p)
{

	int i = min_p-1;
	int j = max_p;
	int v = P[p];
	while (1)
	{
		while (P[++i]<=v);

		while (P[--j]>=v);
			if (j==min_p)
				break;

		if (i>=j)
			break;
		else
			swap (&P[j],&P[i]);
	}
	if (p>i)
		swap (&P[i],&P[p]);
	if (p<i)
		swap (&P[j],&P[p]);
	return i;
}

void QSL(int P[], int min_p, int max_p)
{

	if (max_p <= min_p)
		return;
	int n;
   	n = part(P,min_p,max_p,max_p);
	QSL(P,min_p,n-1);
	QSL(P,n+1,max_p);
}

void QSR(int P[], int min_p, int max_p, int p)
{
	int p1;
	int p2;


	if (max_p <= min_p)//sort check
		return;

	printf("Give the pivot between 0 and %d\n", length); //here there is a kind of bug, but the implementation was easier with this way
	do{
		scanf("%d", &userchoice);
	}while( (userchoice>=0) && (userchoice<=length));
	p1=userchoice;


	int n;
  	/*n = part(P,min_p,max_p,p);

	p1=p-min_p;
	p2=max_p-p+1;
	*/

	QSR(P,min_p,max_p,p1);

	printf("Give the pivot between 0 and %d\n", length); //here there is a kind of bug, but the implementation was easier with this way
	do{
		scanf("%d", &userchoice);
	}while( (userchoice>=0) && (userchoice<=length));
	p2=userchoice;
	QSR(P,n+1,max_p,p2);






	/*int p1;
	int p2;

	if (max_p <= min_p)
		return;
	int n;
   	n = part(P,min_p,max_p,p);

	p1 = ((n-1+min_p)*rand()/RAND_MAX)+min_p;
	p2 = ((max_p-n-1)*rand()/RAND_MAX)+n+1;

	QSR(P,min_p,n-1,p1);
	QSR(P,n+1,max_p,p2);
	*/
}


//mergesort numbers array
void mergeSort(int *array,int left, int right){
	int middle;
	if (left!=right){
		middle=(right+left)/2;
		mergeSort(array,left,middle); //mergesort sort left half array
		mergeSort(array,middle+1,right); //mergesort sort right half array
		merge(array,left,middle,right); //merge arrays
	}
}

//merge the first half array from left to middle index, with the second half array from middle+1 to right index
void merge(int *array, int left, int middle, int right) {
	int ileft=left;
	int	iright=middle+1;
	int	itemp=left;
	int *temp=(int *)malloc((right+2)*sizeof(int));

	while (ileft<=middle && iright<=right) {
		if (array[ileft] <= array[iright]) {
			temp[itemp] = array[ileft];
			itemp++;
			ileft++;
		} else {
			temp[itemp] = array[iright];
			itemp++;
			iright++;
		}
	}
	while (ileft<=middle) {
		temp[itemp]=array[ileft];
		itemp++;
		ileft++;
	}
	while (iright<=right) {
		temp[itemp]=array[iright];
		itemp++;
		iright++;
	}
	for (itemp=left;itemp<=right;itemp++){
		array[itemp] = temp[itemp];
	}
}

void sort(int arr[], int beg, int end,int p) {
	int piv = p/100*end;
	if (end > beg + 1) {
		int l = beg + 1, r = end;

		while (l < r) {
			if (arr[l] <= piv)
				l++;
			 else
				swap(&arr[l], &arr[--r]);
		} swap(&arr[--l], &arr[beg]);

		sort(arr, beg, l,piv);
		sort(arr, r, end,piv);
	}
}

//void swap(int *a, int *b) { int t=*a; *a=*b; *b=t; }