Jump to content
  • Advertisement
Sign in to follow this  
mfawcett

sort k smallest elements

This topic is 4520 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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!