0
$\begingroup$

I'm looking for an existing algorithm that would ensure that the first k elements after sorting are the top k elements but not necessarily in the right order.

To put it differently, I would like an algorithm that acts like C++ std::partial_sort but takes advantage of the fact that I don't need the first elements ordered.

If there's no such thing yet, I'm planning on studying again existing algorithms and try to find out which one would be the best candidate to tweak. Any lead would be welcome.

$\endgroup$
1
  • 2
    $\begingroup$ Find the $k$th largest element in linear time. Run PARTITION with respect to that element. $\endgroup$ Mar 14, 2021 at 13:41

1 Answer 1

0
$\begingroup$

What I was looking for is a selection algorithm that will select the k-th element. As mentioned in comment, running then a simple partition algorithm if needed will then provide the expected result.

The reference seems to be the quick select algorithm while the reference implementation points to introselect as implemented in Numpy's partition function or C++ nth_element function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.