Sign in to follow this  

sort k smallest elements

This topic is 4301 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm having problems understanding the quicksortSmallestK code snippet posted at Developing for Developers, specifically, what their partition function does. This is my C++ interpretation so far (which doesn't work).
template <typename RAC>
void sort_n(RAC &a, typename RAC::iterator left, typename RAC::iterator right, int k)
{
	while (right > left)
	{
		int index = std::distance(a.begin(), left) + std::distance(left, right) / 2;
		typename RAC::iterator iter = std::partition(left, right,
			std::bind2nd(std::less<typename RAC::value_type>(), a[index]));

		if (k <= std::distance(a.begin(), iter))
			right = iter - 1;
		else if (iter - left > right - iter)
		{
			std::sort(iter + 1, right);
			right = iter - 1;
		}
		else
		{
			std::sort(left, iter - 1);
			left = iter + 1;
		}
	}
}



So, question 1: Is this the generally accepted optimal algorithm for finding the smallest k elements in an unsorted random access container? Question 2: Is my interpretation of their partition correct (i.e. partition the array into two segments, one less than the element, one greater than or equal to the element)? The obvious easy way to find the smallest k elements is to populate a priority queue (or max heap, whatever) with the first k elements in the unsorted range, then iterate through the remainder of the unsorted range, checking against the current worst in the sorted range. This is sub-optimal though. I'd like the optimal solution for finding the smallest k elements in an unsorted range. My other issue is, what is the preferred method of finding the best pivot point. Currently I'm just choosing the middle of the range. I would guess finding the median value would be best, but that would require an iteration through the range. Is this generally worth it?

Share this post


Link to post
Share on other sites
Actually, I looked at that function earlier, but I was mis-interpreting how the SortEnd parameter was being used by the algorithm. It does indeed work now.

Share this post


Link to post
Share on other sites

This topic is 4301 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this