#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>

//Generates random numbers and assigns them to the array
void fillArray(int* arr, int size) {
	for (int i = 0; i < size; i++) {
		arr[i] = rand() % size;
	}
}



//Performs Bubble Sort on the array passed through parameter
void bubbleSort(int *arr, int size) {
	for (int i = 0; i < size - 1; i++) {
		for (int j = 0; j < size - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}



//Performs Selection Sort on the array passed through parameter
void selectionSort(int *arr, int size) {
	for (int i = 0; i < size; i++) {
		int minIdx = i;
		for (int j = i; j < size; j++) {
			if (arr[j] < arr[minIdx]) {
				minIdx = j;
			}
		}
		//swap
		int tmp = arr[i];
		arr[i] = arr[minIdx];
		arr[minIdx] = tmp;
	}
}



//Performs Insertion Sort on the array passed through parameter
void insertionSort(int *arr, int size) {
	for (int i = 0; i < size; i++) {
		int curr = arr[i];
		int j = i;
		for (j = i; j > 0 && arr[j - 1] > curr; j--) {
			arr[j] = arr[j - 1];
		}
		arr[j] = curr;
	}
}



void heapify(int *arr, int n, int i)
{
	int largest = i; // Initialize largest as root 
	int l = 2 * i + 1; // left = 2*i + 1 
	int r = 2 * i + 2; // right = 2*i + 2 

	// If left child is larger than root 
	if (l < n && arr[l] > arr[largest])
		largest = l;

	// If right child is larger than largest so far 
	if (r < n && arr[r] > arr[largest])
		largest = r;

	// If largest is not root 
	if (largest != i)
	{
		std::swap(arr[i], arr[largest]);

		// Recursively heapify the affected sub-tree 
		heapify(arr, n, largest);
	}
}



//Performs Heap Sort on the array passed through parameter
//Acts as a wrapper function
void heapSort(int *arr, int size) {
	// Build heap (rearrange array) 
	for (int i = size / 2 - 1; i >= 0; i--)
		heapify(arr, size, i);

	// One by one extract an element from heap 
	for (int i = size - 1; i >= 0; i--)
	{
		// Move current root to end 
		std::swap(arr[0], arr[i]);

		// call max heapify on the reduced heap 
		heapify(arr, i, 0);
	}
}



//Performs Quick Sort on the array passed through parameter
void quickSort(int *arr, int left, int right) {
	int leftIdx = left, rightIdx = right;
	int tmp;
	int pivot = arr[(left + right) / 2];

	/* partition */
	while (leftIdx <= rightIdx) {
		while (arr[leftIdx] < pivot)
			leftIdx++;

		while (arr[rightIdx] > pivot)
			rightIdx--;

		if (leftIdx <= rightIdx) {
			tmp = arr[leftIdx];
			arr[leftIdx] = arr[rightIdx];
			arr[rightIdx] = tmp;
			leftIdx++;
			rightIdx--;
		}
	};

	/* recursion */
	if (left < rightIdx)
		quickSort(arr, left, rightIdx);

	if (leftIdx < right)
		quickSort(arr, leftIdx, right);
}



void merge(int *arr, std::vector<int>& tmp, int start, int start2, int end) {
	int lptr = start;
	int rptr = start2;
	int i = start;
	while (lptr < start2 && rptr <= end) {
		if (arr[lptr] < arr[rptr])
			tmp[i++] = arr[lptr++];
		else
			tmp[i++] = arr[rptr++];
	}
	while (lptr < start2) {
		tmp[i++] = arr[lptr++];
	}
	while (rptr <= end) {
		tmp[i++] = arr[rptr++];
	}
	for (i = start; i <= end; i++) {
		arr[i] = tmp[i];
	}
}



//this function sorts arr from index start to end
void mergeIndexSort(int* arr, std::vector<int>& tmp, int start, int end) {
	if (start < end) {
		int mid = (start + end) / 2;
		mergeIndexSort(arr, tmp, start, mid);
		mergeIndexSort(arr, tmp, mid + 1, end);
		merge(arr, tmp, start, mid + 1, end);
	}
}



//Acts as a wrapper function
void mergeSort(int* arr, int size) {
	std::vector<int> tmp(size);
	//call mergeSort with the array, the temporary
	//and the starting and ending indices of the array
	mergeIndexSort(arr, tmp, 0, size - 1);
}


void print(int *arr, int size){
	for (int i = 0; i < size; i++) {
		std::cout << arr[i] << " ";
	}
	std::cout << std::endl;
}



int main(int argc, char *argv[]) {

	//Get the size of the array
	int n = std::atoi(argv[1]);

	// Create 6 arrays of size n and allocate memory for them
	int *bubbleArray = new int[n];
	int *selectionArray = new int[n];
	int *insertionArray = new int[n];
	int *heapArray = new int[n];
	int *mergeArray = new int[n];
	int *quickArray = new int[n];

	//Fill the array with randomly generated numbers
	fillArray(bubbleArray, n);
	//print(bubbleArray, n);

	//COPY the values to the other
	//This adds consistency among the elements of the array
	std::memcpy(selectionArray, bubbleArray, n*sizeof(int));
	std::memcpy(insertionArray, bubbleArray, n * sizeof(int));
	std::memcpy(heapArray, bubbleArray, n * sizeof(int));
	std::memcpy(mergeArray, bubbleArray, n * sizeof(int));
	std::memcpy(quickArray, bubbleArray, n * sizeof(int));

	//Call the sorting algorithms 1 by 1 with their respecive array
	bubbleSort(bubbleArray, n);
	std::cout << "Bubble Sort performed." << std::endl;
	selectionSort(selectionArray, n);
	print(heapArray, n);
	std::cout << "Selection Sort performed." << std::endl;
	insertionSort(insertionArray, n);
	std::cout << "Insertion Sort performed." << std::endl;
	heapSort(heapArray, n);
	std::cout << "Heap Array: ";
	print(heapArray, n);
	std::cout << "Heap Sort performed." << std::endl;
	mergeSort(mergeArray, n);
	std::cout << "Merge Sort performed." << std::endl;
	quickSort(quickArray, 0, n-1);
	std::cout << "Quick Sort performed." << std::endl;


	//Deallocate the arrays
	delete[] bubbleArray;
	delete[] selectionArray;
	delete[] insertionArray;
	delete[] heapArray;
	delete[] mergeArray;
	delete[] quickArray;


	return 0;
}