#include <iostream>
#include <ctime>
#include <fstream>
#define MAX 100
using namespace std;

void CreateRndArr(int a[], int n)
{
	int const l = 0, r = 99;
	srand(time(0));
	for (int i = 0; i < n; i++)
	{
		a[i] = l + rand() % (r - l + 1);
	}
}

#pragma region Sort
void QuickSort(int a[], int left, int right){
	int i, j, x, t;
	x = a[(left + right) / 2]; i = left; j = right;
	do{
		while (a[i] < x) i++;
		while (a[j] > x) j--;
		if (i <= j) {
			t = a[i]; a[i] = a[j]; a[j] = t;
			i++; j--;
		}
	} while (i < j);
	if (left < j) QuickSort(a, left, j);
	if (i < right) QuickSort(a, i, right);
}

void Shift(int a[], int l, int r){
	int i = l, j = 2 * i + 1, x = a[i];
	while (j <= r){
		if (j < r && a[j] < a[j + 1])
			j++;
		if (a[j] <= x)
			return;
		else {
			a[i] = a[j]; a[j] = x;
			i = j; j = 2 * i + 1; x = a[i];
		}
	}
}

void CreateHeap(int a[], int n){
	int l = n / 2 - 1;
	while (l >= 0) {
		Shift(a, l, n - 1);
		l = l - 1;
	}
}

void HeapSort(int a[], int n){

	int r;
	CreateHeap(a, n);
	r = n - 1;
	while (r > 0) {
		int t = a[0]; a[0] = a[r]; a[r] = t;
		r--;
		if (r > 0) Shift(a, 0, r);
	}
}

void ShellSort(int a[], int n){
	int i, j, x, h = 1;
	while (h <= n / 3) h = h * 3 + 1;
	while (h > 0){
		for (i = h; i < n; i++){
			x = a[i];
			j = i - h;
			while ((x < a[j]) && (j >= 0)){
				a[j + h] = a[j]; j = j - h;
			}
			a[j + h] = x;
		}
		h = (h - 1) / 3;
	}
}

void merge(int a[], int first, int mid, int last) {
	int temp[MAX], first1, last1, first2, last2, i = first;
	first1 = first; last1 = mid; first2 = mid + 1; last2 = last;
	while ((first1 <= last1) && (first2 <= last2))
		if (a[first1] < a[first2])
			temp[i++] = a[first1++];
		else
			temp[i++] = a[first2++];
	while (first1 <= last1) temp[i++] = a[first1++];
	while (first2 <= last2) temp[i++] = a[first2++];
	for (i = first; i <= last; i++)
		a[i] = temp[i];
}
void mergeSort(int a[], int first, int last) {
	if (first < last) {
		int mid = int((first + last) / 2);
		mergeSort(a, first, mid);
		mergeSort(a, mid + 1, last);
		merge(a, first, mid, last);
	}
}

void RadixSort(int a[], int n){
	const int m = 5;
	int digit, num, h = 10, B[10][MAX], Len[10];
	for (int d = 0; d < m; d++){
		for (int i = 0; i < 10; i++) Len[i] = 0;
		for (int i = 0; i < n; i++){
			digit = (a[i] % h) / (h / 10);
			B[digit][Len[digit]++] = a[i];
		}
		num = 0;
		for (int i = 0; i < 10; i++)
			for (int j = 0; j < Len[i]; j++)
				a[num++] = B[i][j];
		h *= 10;
	}
}

#pragma endregion 


void XuatArr(int a[], int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << "\t";
	}
}

int SequentialSearch(int A[], int n, int x)
{
	for (int i = 0; i < n; i++)
		if (A[i] == x) return 1;
	return 0;
}

int BinarySearch(int a[], int n, int x)
{
	int mid, left = 0, right = n - 1;
	do
	{
		mid = (left + right) / 2;
		if (a[mid] == x) return 1;
		else
			if (a[mid] < x) left = mid + 1;
			else right = mid - 1;
	} while (left <= right);
	return 0;
}


void GhiFileText(int a[], int n)
{
	fstream FileNumOut("sv.txt", ios::out);
	if (FileNumOut.is_open()){
		for (int i = 0; i < n; i++){
			FileNumOut << a[i] << " ";
		}
		cout << "Ghi file thanh cong!" << endl;
	}
	else
		cout << "\nKhong the mo file!" << endl;
	FileNumOut.close();
}
void DocFileText(int a[], int n)
{
	fstream FileNumIn("sv.txt", ios::in);
	for (int i = 0; i < n; i++)
	{
		FileNumIn >> a[i];
	}
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	FileNumIn.close();
}


void GhiFileBinary(int a[], int n)
{
	fstream FileNumBinary("sv2.txt", ios::binary | ios::out);
	if (FileNumBinary.is_open())
	{
		for (int i = 0; i < n; i++)
		{
			FileNumBinary.write(reinterpret_cast<char *>(&a[i]), sizeof(int));
		}
		cout << "Ghi file binary thang cong!" << endl;
	}
	else
		cout << "Ghi file binary that bai!" << endl;
	FileNumBinary.close();
}
void DocFileBinary(int a[], int n)
{
	fstream FileNumBinary("sv2.txt", ios::binary | ios::in);
	if (FileNumBinary.is_open())
	{
		FileNumBinary.read(reinterpret_cast<char*>(a), sizeof(int)*n);
		cout << "\nDoc file binary thang cong!" << endl;
	}
	else
		cout << "Doc file binary that bai!" << endl;
	FileNumBinary.close();
	XuatArr(a, n);
}

void Menu()
{
	int a[100], n;
	int sl;
	cout << "Create Arr : " << endl;
	cout << "Nhap vao so luong phan tu cua mang:= ";
	cin >> n;
	cout << endl;
	CreateRndArr(a, n);
	system("cls");
	cout << "Mang khi chua sap xep!" << endl;
	XuatArr(a, n);
	cout << endl;
	int sls, slr, slf, x;
	do
	{
	bal:
		cout << "1.Sort \n2.Search \n3.Read,Write File \n0.Exit" << endl;
		cout << "Nhap vao lua chon:= ";
		cin >> sl;
		system("cls");
		switch (sl)
		{
		case 1:
			cout << "\n1.QuickSort \n2.HeapSort \n3.ShellSort \n4.MergeSort \n5.RadixSort \n0.Back" << endl;
			cout << "Nhap vao lua chon:= ";
			cin >> sls;
			system("cls");
			switch (sls)
			{
			case 1:
				cout << "Mang sau khi sap xep voi QuickSort!" << endl;
				QuickSort(a, 0, n - 1);
				XuatArr(a, n);
				cout << endl;
				break;
			case 2:	
				cout << "Mang sau khi sap xep voi HeapSort!" << endl;
				HeapSort(a, n);
				XuatArr(a, n);
				cout << endl;
				break;
			case 3:
				cout << "Mang sau khi sap xep voi ShellSort!" << endl;
				ShellSort(a, n);
				XuatArr(a, n);
				cout << endl;
				break;
			case 4:
				cout << "Mang sau khi sap xep voi MergeSort!" << endl;
				mergeSort(a, 0, n - 1);
				XuatArr(a, n);
				cout << endl;
				break;
			case 5:
				cout << "Mang sau khi sap xep voi RadixSort!" << endl;
				RadixSort(a, n);
				XuatArr(a, n);
				cout << endl;
				break;
			default:
				break;
			}
			break;
		case 2:
			cout << "1.Sequentia lSearch \n2.Binary Search \n0.Back" << endl;
			cout << "Nhap vao lua chon:= ";
			cin >> slr;
			system("cls");
			switch (slr)
			{
			case 1:
				cout << "Tim kiem voi Sequential Search!" << endl;
				cout << "Nhap vao phan tu muon tim:= ";
				cin >> x;
				if (SequentialSearch(a, n, x) == 1){
					cout << x << " co trong mang!" << endl;
					goto bal;
				}
				else{
					cout << x << " khong co trong mang" << endl;
					goto bal;
				}
			case 2:
				cout << "Tim kiem voi Binary Search!" << endl;
				cout << "Nhap vao phan tu muon tim:= ";
				cin >> x;
				if (BinarySearch(a, n, x) == 1){
					cout << x << " co trong mang!" << endl;
					goto bal;
				}
				else{
					cout << x << " khong co trong mang" << endl;
					goto bal;
				}
			default:
				break;
			}break;
		case 3:
			cout << "1.Write File \n2.Read File \n0.Back" << endl;
			cout << "Nhap vao lua chon:= ";
			cin >> slf;
			switch (slf)
			{
			case 1:
				cout << "Write File" << endl;
				GhiFileText(a, n);
				goto bal;
			case 2:
				cout << "Read File" << endl;
				DocFileText(a, n);
				goto bal;
			default:
				goto bal;
			}
		default:
			break;
		}
	} while (sl == 1);
}
int main()
{
	Menu();
	/*GhiFileBinary(a, n);

	DocFileBinary(a, n);*/
	system("pause");
	return 0;
}