Quick-select algorithm to find the n-smallest elements.

n-smallest.cpp

template<typename Iterator>
Iterator part(Iterator begin, Iterator end)
{
	auto pivot = begin++;
	
	if (pivot == begin || begin == end) return pivot;
	
	for (--end; begin != end; ++begin)
	{
		while (begin != end && *begin < *pivot) ++begin;
		
		while (begin != end && *end > *pivot) --end;
		
		if (begin == end) break;
		
		std::swap(*begin, *end);
	}
	
	if (*begin > *pivot) --begin;
	
	std::swap(*begin, *pivot);
	
	return begin;
}

template<typename Iterator>
Iterator smallest_n(Iterator begin, Iterator end, std::size_t position)
{
	if (begin == end || position == 0) return begin;
	
	else if (std::distance(begin, end) <= position) return end;
	
	while (true)
	{
		auto i = part(begin, end);
		
		auto distance = std::distance(begin, i);
		
		if (distance < position)
		{
			position -= (distance + 1);
			
			begin = ++i;
		}
		
		else if (distance > position) end = i;
		
		else return i;
	}
}