Unoptimized single-function versions of quicksort.

quick-sort.hpp

#ifndef QUICK_SORT_SINGLE_FUNCTION_HPP
#define QUICK_SORT_SINGLE_FUNCTION_HPP

#include <iterator>
#include <utility>

template<typename Iterator>
void quick_sort(Iterator begin, Iterator end)
{
	if (begin == end || std::next(begin) == end) return;
	
	auto i = std::next(begin);
	
	for (auto j = std::prev(end); i != j; ++i)
	{
		while (i != j && *i < *begin) ++i;
		
		while (i != j && *j > *begin) --j;
		
		if (i == j) break;
		
		std::swap(*i, *j);
	}
	
	if (*i > *begin) --i;
	
	std::swap(*i, *begin);
	
	quick_sort(begin, i);
	
	quick_sort(++i, end);
}

#endif /* QUICK_SORT_SINGLE_FUNCTION_HPP */