# 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.

## 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 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.

1. 1
2. 2
3. 3
Rutin
22
4. 4
JoeJ
16
5. 5

• 14
• 30
• 13
• 11
• 11
• ### Forum Statistics

• Total Topics
631774
• Total Posts
3002295
×