//Sortieralgorithmen and creating an array with m elements, m is entered by the user
#include <iostream>
#include <cstdlib>	//rand() is here, returns int between 0 and RAN_MAX

using namespace std;

void swap(int, int, int *);				// swap two elements in the array

void menu();									//prints the main menu

void Show_array(int *, int);				// prints the array

void size_array(int *);					// creates an array


//Sorting Aldorithms
void Direct_Search(int *, int);			//"Direct Search"

void Direct_Insert(int *, int);			//"Direct Insert"

void Binary_Insert(int *, int);			//"Binary Insert"

void Bubble_Sort(int *, int);				//"Bubble Sort"

void Shell_Sort(int *, int);				//"Shell Sort"

void Quick_Sort(int *, int, int, int);	//"Quick Sort"


int main()
{	int choice = 9;
	int size=1;							//number of digits in the array
	int *psize = &size;
	int *parray = new int [size];

	system("clear");

	do
	{	menu();
		cin >> choice;

		if (choice != 0)
		{	switch (choice)
			{	case 1: { size_array(psize);
							 delete[] parray;
							 parray = new int [size];

								for(int i=0; i<size; i++)
								{	parray[i] = rand(); }
						  }
						break;
				case 2: Show_array(parray,size);
						break;
				case 3: Direct_Search(parray,size);
						break;
				case 4: Direct_Insert(parray,size);
						break;
				case 5: Binary_Insert(parray,size);
						break;
				case 6: Bubble_Sort(parray,size);
						break;
				case 7: Shell_Sort(parray,size);
						break;
				case 8: Quick_Sort(parray,size,0,size-1);
						break;
				default:
						{	system("clear");
							cout << "\nWrong Input!\n";
						}
			}
		}
	}while (choice != 0);

	cout << "\nGood Bye!\n";
	return 0;
}


void menu()
{	cout << "\nMain Menu:\n";
	cout << "Create an array:\t\t1\n";
	cout << "Show array:\t\t\t2\n";
	cout << "Sort with \"Direct Search\":\t3 \n";
	cout << "Sort with \"Direct Insert\":\t4 \n";
	cout << "Sort with \"Binary Insert\":\t5 \n";
	cout << "Sort with \"Bubble-Sort\":\t6 \n";
	cout << "Sort with \"Shell-Sort\":\t\t7 \n";
	cout << "Sort with \"Quick-Sort:\"\t\t8 \n";
	cout << "Exit:\t\t\t\t0 \n";
	cout << "\nEnter(0-8)>> ";
}


void size_array(int *psize)	// creates an array with m random digits
{	system("clear");
	cout <<	"\nHow many digits must the array have: ";
	cin >> *psize;
	system("clear");
}


void Show_array(int *parray, int size)
{	system("clear");
	cout << "\nThe array is now: ";

	for(int i=0; i<size; i++)
	{	cout << parray[i] << " ";}

	cout << "\n\n";
}


void swap(int k, int j, int *parray)
{	int buffer;

	buffer = parray[k];
	parray[k] = parray[j];
	parray[j] = buffer;
}


void Direct_Search(int *parray, int size)	//gets pointer to the array and its size
{	int k=0;

	for (int i = 0; i < size - 1; i++)
	{	k = i;
		for (int j = i + 1; j < size; j++)
			if (parray[j] < parray[k])
				k = j;
		swap(k,i,parray);						//swap the elements k and i in parray
	}

	system("clear");
	cout << "\nThe array was sorted with \"Direct Search\" algorithm\n\n";
}


/* Direct-Insert sucht fuer jedes Element 1 <= i <= n diejenige Stelle j
im zu sortierenden Feld, fuer die gilt:
sortfeld [j-1] < sortfeld[j] <= others
d.h. fuer jedes Element wird versucht, es "soweit wie moeglich noch
vorn" zu schieben.
Abbruchkriterium: Elemente "davor kleiner oder Feld zu Ende"
*/
void Direct_Insert(int *parray, int size)
{	int k = 0;
	int buffer = 0;

	for (int i = 1; i < size; i++)
	{	buffer = parray[i];
		k = i;

		while (( buffer < parray[k-1]) && (k >= 1))
		{	parray[k] = parray[k-1];
			k--;
		}

		parray[k] = buffer;
	}

	system("clear");
	cout << "\nThe array was sorted with \"Direct Insert\" algorithm\n\n";
}


void Binary_Insert(int *parray, int size)
{	int middle, l, r;
	int buffer;

	for (int i = 1; i < size; i++)
	{	buffer = parray[i];
		l = 0;
		r = i;

		while (l < r)
		{	middle = (l + r) / 2;

			if (parray[middle] <= buffer)
				l = middle + 1;
			else
				r = middle;
		}

		for (int j = i; j >= r+1; j --)
			parray[j] = parray[j-1];

		parray[r] = buffer;
	}

	system("clear");
	cout << "\nThe array was sorted with \"Binary Insert\" algorithm\n\n";
}


void Bubble_Sort(int *parray, int size)
{	for (int i = 1; i < size; i++)
		for (int j = size-1; j >= i; j--)
			if ( parray[j-1] > parray[j])
				swap(j-1,j,parray);

	system("clear");
	cout << "\nThe array was sorted with \"Bubble Sort\" algorithm\n\n";
}


/* Hier wird versucht, Austauschoperationen ueber Distancen,
zu vollziehen, die so "gross" wie moeglich sind.
Guenstig sind Werte von h = h * 5 + 1 (fuer h(1) = 1)
*/
void Shell_Sort(int *parray, int size)
{	int i, j, increment, temp;
	increment = 3;

	while (increment > 0)
	{	for (i=0; i < size; i++)
			{	j = i;
			temp = parray[i];

			while ((j >= increment) && (parray[j-increment] > temp))
			{	parray[j] = parray[j - increment];
				j = j - increment;
			}

			parray[j] = temp;
			}

		if (increment/2 != 0)
			increment = increment/2;
		else if (increment == 1)
			increment = 0;
		else
			increment = 1;
  }

	system("clear");
	cout << "\nThe array was sorted with \"Shell Sort\" algorithm\n\n";
}


void Quick_Sort(int * parray, int size, int L, int R)
{	int buffer;
	int left = L, right = R;

	buffer = parray[(left + right) / 2];

	do
	{	while (parray[left] < buffer)
		{	left++; }

		while (parray[right] > buffer)
		{	right--; }

		if (left <= right)
		{	if (left < right)
			{	swap(left,right,parray); }

			left++;
			right--;
		}
	}	while(left <= right);


	if ( L < right )
	{	Quick_Sort(parray, size, L, right); }

	if ( R > left )
	{	Quick_Sort(parray, size, left, R); }

	system("clear");
	cout << "\nThe array was sorted with \"Quick Sort\" algorithm\n\n";
}