#include "sorting.h"

namespace sorting {

	void swap(int* input, int* tmp) {
		int t = *input;
		*input = *tmp;
		*tmp = t;
	}

	//************
	// QuickSort *
	//************
	int partition(vector<int>& a, int low, int high) {
		int pivot = a[high]; 	// pivot/ das Element an der höchsten Stelle
		int i = (low - 1);	   	// Index des Elements an der niedrigsten Stellen

		// vom niedrigsten zum höchsten Element durchgehen
		for (int j = low; j < high; j++) {
			// aktuelles Element kleiner als Pivot?
			if (a[j] < pivot) {
				i++; // index des kleineren Elements erhöhen
				std::swap(a[i], a[j]);
			}
		}
		std::swap(a[i + 1], a[high]);
		return (i + 1);
	}

	void QuickSort(vector<int>& arr, int left, int right) {
		if (left < right) {
			int pi = partition(arr, left, right);
			QuickSort(arr, left, pi - 1);
			QuickSort(arr, pi + 1, right);
		}
	}

	//************
	// MergeSort *
	//************
	void Merge(vector<int>& a, vector<int>& b, int low, int pivot, int high) {
		int left, right, pos;
		left = low;
		pos = low;
		right = pivot + 1;

		// Mische die Teilfolge in tmp
		while (left <= pivot && right <= high) {
			if (a[left] < a[right]) {
				b[pos++] = a[left++];
			}
			else {
				b[pos++] = a[right++];
			}
		}
		// falls rechts fertig übernehme Rest von links
		while (left <= pivot) {
			b[pos++] = a[left++];
		}
		// links fertig übernehme Rest von rechts
		while (right <= high) {
			b[pos++] = a[right++];
		}
		//-------------
		// kopiere tmp in input zurück
		for (left = low; left < pos; left++)
			a[left] = b[left];
	}

	void MergeSort(vector<int>& a, vector<int>& b, int low, int high) {
		int mid;
		// Aufteilen wenn l<h
		if (low < high) {
			mid = (low + high) / 2;
			MergeSort(a, b, low, mid);
			MergeSort(a, b, mid + 1, high);
			// nach dem teilen
			Merge(a, b, low, mid, high);
		}
	}

	void natMerge(std::vector<int>& a, std::vector<int>& b, int left, int middle, int right) {
		int i = left, j = middle + 1, k = left;

		while (i <= middle && j <= right) {
			if (a[i] <= a[j]) {
				b[k++] = a[i++];
			}
			else {
				b[k++] = a[j++];
			}
		}

		while (i <= middle) {
			b[k++] = a[i++];
		}

		while (j <= right) {
			b[k++] = a[j++];
		}

		for (i = left; i <= right; i++) {
			a[i] = b[i];
		}
	}

	void natMergeSort(std::vector<int>& a, std::vector<int>& b) {
		int n = a.size();
		int left, middle, right;

		while (true) {
			left = 0;
			bool merged = false;

			while (left < n) {
				middle = left;
				while (middle < n - 1 && a[middle] <= a[middle + 1]) {
					middle++;
				}

				if (middle == n - 1) {
					break;
				}

				right = middle + 1;
				while (right < n - 1 && a[right] <= a[right + 1]) {
					right++;
				}

				Merge(a, b, left, middle, right);
				merged = true;
				left = right + 1;
			}

			if (!merged) {
				break;
			}
		}
	}

	//************
	// Heapsort  *
	//************
	void heapify(vector<int>& a, int n, int i) {
		int largest = i;   // Initialize largest as root
		int l = 2 * i + 1; // left child = 2*i + 1
		int r = 2 * i + 2; // right child = 2*i + 2

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

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

		// If largest is not root
		if (largest != i) {
			swap(&a[i], &a[largest]);

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

	void HeapSort(vector<int>& a, int n) {
		// create Heap
		for (int i = n / 2 - 1; i >= 0; i--)
			heapify(a, n, i);

		for (int i = n - 1; i >= 0; i--) {
			// Move current root to end
			swap(&a[0], &a[i]);

			// reduce heap
			heapify(a, i, 0);
		}
	}

	//************
	// Shellsort *
	//************
	// Hier soll Hibbard implementiert werden
	void ShellSort_2n(vector<int>& a, int n) {
		int N = a.size();
		int h = 1;
		while (h < N / 3) {
			h = 2 * h + 1; // Hibbard-Folge
		}
		// Schleife über die Abstandsfolge
		while (h >= 1) {
			// Insertion Sort von Elementen mit Abstand gap
			for (int i = h; i < N; i++) {
				int tmp = a[i];
				int j = i;
				while (j >= h && tmp < a[j - h]) {
					a[j] = a[j - h];
					j -= h;
				}
				a[j] = tmp;
			}
			h /= 2;
			// Elemente sind im Abstand gap sortiert
		}
	}

	void ShellSort_3n(vector<int>& a, int n) {
		int N = a.size();
		int h = 1;
		while (h < N / 3) {
			h = 3 * h + 1; // Hibbard-Folge
		}
		while (h >= 1) {
			for (int i = h; i < N; i++) {
				int tmp = a[i];
				int j = i;
				while (j >= h && a[j - h] > tmp) {
					a[j] = a[j - h];
					j -= h;
				}
				a[j] = tmp;
			}
			h /= 3;
		}
	}

	void randomizeVector(vector<int>& array, int n) {
		array.resize(n);

		for (unsigned int i = 0; i < array.size(); i++)
			array[i] = rand() % 1000000;
	}

}
