#include<iostream>
#include<ctime>
using namespace std;

void fillArr(int* arr, int n)
{
		for (int i = 0; i < n; i++)
		{
				arr[i] = (rand()*rand()) % 65536;
		}
}

void outArr(int* arr, int n)
{
		cout << "\nArray:" << endl;
		for (int i = 0; i < n; i++)
		{
				cout << arr[i] << endl;
		}
}

void BubbleSort(int* arr, int n)
{
		for (int i = 0; i < n - 1; i++)
				for (int j = 0; j < n - i - 1; j++)
				{
						if (arr[j] > arr[j + 1])
						{
								int temp = arr[j];
								arr[j] = arr[j + 1];
								arr[j + 1] = temp;
						}
				}
}

void qSort(int* arr, int begin, int end)
{
		int left = begin;
		int right = end;
		int pivot = arr[((left + right) / 2)];
		while (left <= right)
		{
				while (arr[left] < pivot) left++;
				while (arr[right] > pivot) right--;
				if (left <= right)
				{
						int temp = arr[left];
						arr[left] = arr[right];
						arr[right] = temp;
						left++;
						right--;
				}
		}

		if (end > left) qSort(arr, left, end);
		if (begin < right)qSort(arr, begin, right);
}

void ShellSort(int *arr, int n)
{
	int i,j,k;
	for(i=n/2;i>0;i/=2)
		for(j=i;j<n;j++){
			int temp = arr[j];
			for(k=j;k>=i;k-=i){
				if(temp<arr[k-i])
					arr[k] = arr[k-i];
				else break;
			}
			arr[k] = temp;
		}

}


int main()
{
		int n;
		char qwe;
		cout << "We ask you to enter the size of an array:";
		cin >> n;
		int *arr1 = new int[n];
		int *arr2 = new int[n];
		int *arr3 = new int[n];

		fillArr(arr1, n);

		for (int i = 0; i < n; i++)
		{
				arr2[i] = arr1[i];
				arr3[i] = arr1[i];
		}

		cout << "Shall we print the original aray? y/n\n";
		cin >> qwe;
		if (qwe == 'y') outArr(arr1, n);

		unsigned long t = clock();
		BubbleSort(arr1, n);
		unsigned long y = clock();

		cout << "Shall we print the BubbleSorted aray? y/n\n";
		cin >> qwe;
		if (qwe == 'y') outArr(arr1, n);
		cout << "Time: " << ((double)y / CLOCKS_PER_SEC) - ((double)t / CLOCKS_PER_SEC) << endl;

		t = clock();
		qSort(arr2, 0, n - 1);
		y = clock();

		cout << "Shall we print the QuickSorted aray? y/n\n";
		cin >> qwe;
		if (qwe == 'y') outArr(arr2, n);
		cout << "Time: " << ((double)y / CLOCKS_PER_SEC) - ((double)t / CLOCKS_PER_SEC) << endl;

		t = clock();
		ShellSort(arr3, n);
		y = clock();

		cout << "Shall we print the ShellSorted aray? y/n\n";
		cin >> qwe;
		if (qwe == 'y') outArr(arr3, n);
		cout << "Time: " << ((double)y / CLOCKS_PER_SEC) - ((double)t / CLOCKS_PER_SEC) << endl;

		cout << "We thank you for using our product. Until next time." << endl;

		system("pause");
}