quick_sort.cpp

#include <iostream>
#include <vector>

template <class T>
size_t partition(std::vector<T>& vec, size_t p, size_t q);

template <class T>
void quicksort_util(std::vector<T>& vec, size_t p, size_t r);

template <class T>
void quicksort(std::vector<T>& vec);

template <class T>
void display(T item);

int main(int argc, char* argv[])
{
	std::vector<int> vec{ 1, 2, 34, 2, -3, 4, -1, 0, 4, 3, 5 };

	std::cout << "\nVector size is: " << vec.size() << "\n";
	for (auto item : vec)
	{
		display(item);
	}
	std::cout << "\n";

	quicksort(vec);

	for (auto item : vec)
	{
		display(item);
	}
	std::cout << "\n";

	getchar();
	return 0;
}

template <class T>
size_t partition(std::vector<T>& vec, size_t p, size_t q)
{
	auto x = vec[p];
	auto i = p;

	auto j = p + 1;
	for (; j != q; j++)
	{
		if (vec[j] <= x)
		{
			++i;
			std::swap(vec[i], vec[j]);
		}
	}

	std::swap(vec[p], vec[j]);

	return i;
}

template <class T>
void quicksort_util(std::vector<T>& vec, size_t p, size_t r)
{
	if (p < r)
	{
		auto q = partition(vec, p, r);
		quicksort_util(vec, p, q - 1);
		quicksort_util(vec, q + 1, r);
	}
}

template <class T>
void quicksort(std::vector<T>& vec)
{
	quicksort_util(vec, 0, vec.size() - 1);
}

template <class T>
void display(T item)
{
	std::cout << item << ' ';
}