#include <iostream>
#include <vector>
#include <algorithm>

// Bubble sort

template <class T>
void manualSwap(std::vector<T>& v, int s1, int s2) {
	T temp = v[s1];
	v[s1] = v[s2];
	v[s2] = temp;
}

template <class T>
void bubbleSort(std::vector<T>& v) {
	for (int i = 0; i < v.size(); i++) {
		for (int j = i + 1; j < v.size(); j++) {
			if (v[i] > v[j])
				manualSwap(v, i, j);
		}
	}
}

// Insertion sort

template <class T>
void insertionSort(std::vector<T>& v) {
	for (int i = 1; i < v.size(); i++) {
		for (int j = i; j > 0 && v[j - 1] > v[j]; j--)
			std::swap(v[j], v[j-1]);
	}
}

// Selection sort

template <class T>
void selectionSort(std::vector<T>& v) {
	for (int i = 0, min = 0; i < v.size() - 1; i++, min = i) {
		for (int j = i + 1; j < v.size(); j++) {
			if (v[j] < v[min]) min = j;
		}
		if (i != min) std::swap(v[i], v[min]);
	}
}

// Merge sort

template <class T>
void merge(std::vector<T>& v, int start1, int size1, int start2, int size2) {
	std::vector<T> temp(size1 + size2);
	for (int t = 0, i = 0, j = 0; t < temp.size(); t++) {
		if (j >= size2 || (i < size1 && v[start1 + i] < v[start2 + j]))
			temp[t] = v[start1 + i++];
		else
			temp[t] = v[start2 + j++];
	}

	for (int i = 0; i < temp.size(); i++)
		v[start1 + i] = temp[i];
}

template <class T>
void mergeSort(std::vector<T>& v, int start = 0, int size = -1) {
	if (size == -1) size = v.size();
	if (size < 2) return;

	int mid = size / 2;
	mergeSort(v, start, mid);
	mergeSort(v, start + mid, size - mid);
	merge(v, start, mid, start + mid, size - mid);
}

// Quick sort

template <class T>
void quickSort(std::vector<T>& v, int start = 0, int pivot = -1) {
	if (pivot == -1) pivot = v.size() - 1;
	if (pivot <= start) return;

	int end = pivot;
	for (int i = start; i < pivot; i++) {
		if (v[i] > v[pivot]) {
			if (pivot - i > 1) // if pivot and i aren't next to each other, make space for i on the right of pivot
				std::swap(v[pivot-1], v[pivot]);
			std::swap(v[i], v[pivot]);
			i--;
			pivot--;
		}
	}
	quickSort(v, start, pivot - 1);
	quickSort(v, pivot + 1, end);
}

// Count sort

void countSort(std::vector<unsigned>& v) {
	unsigned max = 0;
	for (auto num : v) {
		if (num > max) max = num;
	}
	std::vector<int> counts(max + 1);

	for (auto num : v) {
		counts[num]++;
	}

	int prev = 0;
	for (int i = 0; i < counts.size(); i++) {
		counts[i] += prev;
		prev = counts[i];
	}

	for (int i = 0; i < v.size(); i++) {
		if (counts[v[i]] - 1 > i) {
			std::swap(v[i], v[--counts[v[i]]]);
			i--;
		}
	}
}

// main

template <class T>
std::ostream& operator<<(std::ostream& ostr, std::vector<T> vec) {
	for (auto elem : vec)
		ostr << elem << ", ";
	return ostr;
}

int main() {
	std::vector<int> vec1 = { 39, 27, 43, 3, 9, 82, 10 };
	bubbleSort(vec1);
	std::cout << "Bubble:    " << vec1 << std::endl;

	std::vector<int> vec2 = { 39, 27, 43, 3, 9, 82, 10 };
	insertionSort(vec2);
	std::cout << "Insertion: " << vec2 << std::endl;

	std::vector<int> vec3 = { 39, 27, 43, 3, 9, 82, 10 };
	selectionSort(vec3);
	std::cout << "Selection: " << vec3 << std::endl;

	std::vector<int> vec4 = { 39, 27, 43, 3, 9, 82, 10 };
	mergeSort(vec4);
	std::cout << "Merge:     " << vec4 << std::endl;

	std::vector<int> vec5 = { 39, 27, 43, 3, 9, 82, 10 };
	quickSort(vec5);
	std::cout << "Quick:     " << vec5 << std::endl;

	std::vector<unsigned> vec6 = { 39, 27, 43, 3, 9, 82, 10 };
	countSort(vec6);
	std::cout << "Count:     " << vec6 << std::endl;
}