void bubbleSortVolume1(int arr[], int n) {
	for (int i = 0; i < n - 1; i++) { // number of iterations needed
		for (int j = 0; j < n - i - 1; j++) { // iterations for sorted elements;
			if (arr[j] > arr[j + 1]) {
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				//swap(arr[j], arr[j+1]);
			}
		}
	}
}
void bubbleSortVolume2(int arr[], int n) {
	bool sorted;
	do {
		sorted = true; //until the array is not sorted;
		for (int i = 0; i < n - 1; i++) { //number of iterations needed
			if (arr[i] > arr[i + 1]) {
				sorted = false; // there is a swap made
				swap(arr[i], arr[i + 1]);
			}
		}
	} while (sorted == false); // until there is no swaps made
}
//selectionsort - O(n^2)
void selectionSort(int arr[], int n) {
	for (int i = 0; i < n - 1; i++) { // number of iterations/keys;
		int iMin = i; // choosing the key
		for (int j = i + 1; j < n; j++) { //searching for the lowest of the rest to swap with the key;
			if (arr[j] < arr[iMin]) {
				iMin = j;
			}
		}
		if (iMin != i) {
			swap(arr[i], arr[iMin]);
		}
	}
}

//insertion sort - O(n^2)
void insertionSort(int arr[], int n) {
	for (int i = 1; i < n; i++) // for every element;
	{
		int currentIndex = i;
		while (arr[currentIndex] < arr[currentIndex - 1] && currentIndex > 0) { // moving the element to the left until there is a lower number;
			swap(arr[j], arr[j - 1]);
			j--;
		}
	}
}

//merge sort - 0(n * log n) и O(n) - сложност по памет
//изисква допълнителна памет, но е по-бърз за огромни
void merge(int *originalArray, int* mergeArray, int start, int mid, int end) {
	int left = start;
	int right = mid + 1;
	for (int i = start; i <= end; i++)
	{
		if (left <= mid && (right > end || originalArray[left] <= originalArray[right])) // ako vsichki desni sa vzeti veche ili lqvoto chislo e po-malko ot dqsnoto
		{
			mergeArray[i] = originalArray[left];
			left++;
		}
		else { // vuv vsichki drugi sluchai
			mergeArray[i] = originalArray[right];
			right++;
		}
	}
	for (int i = start; i < end; i++) {
		originalArray[i] = mergeArray[i];
	}
}
void _mergeSort(int *originalArray, int *mergeArray, int start, int end) {
	if (start < end) {
		int mid = (start + end) / 2;
		_mergeSort(originalArray, mergeArray, start, mid); // sorting the first half of the array;
		_mergeSort(originalArray, mergeArray, mid + 1, end); // sorting the second half of the array;
		merge(originalArray, mergeArray, start, mid, end); // final merge
	}
}
void mergeSort(int *array, int length) {
	int *mergeArray = new int[length]; // temporary array
	_mergeSort(array, mergeArray, 0, length - 1); // the whole merge sorting for "array"
	delete[] mergeArray;
}