1

I have to implement an algorithm that solves the multi-selection problem. The multiselection problem is:

Given a set S of n elements drawn from a linearly ordered set, and a set K = {k1, k2,...,kr} of positive integers between 1 and n, the multiselection problem is to select the ki-th smallest element for all values of i, 1 <= i <= r

I need to solve the average case on Θ(n log r) I've found a paper that implements the solution I need, but it assumes that there are no repeated numbers on the set S. The problem is that I can't assume that and I don't know how to adapt the algorithm of that paper to support repeated numbers. The paper is here: http://www.ccse.kfupm.edu.sa/~suwaiyel/publications/multiselection_parCom.pdf and the algorithm is on the second page. Any tips are welcome!

Improve this question
3
  • 1
    Why can't you simply sort the set using quicksort and choose the kith elements directly? Not sure if I understand correctly. Commented Sep 29, 2013 at 19:14
  • 1
    @AbhishekBansal because its cost would be Θ(n log n) on the average which is higher than what I'm asked for Commented Sep 29, 2013 at 19:16
  • I have an implementation of this algorithm at github.com/jmlundberg/nth_element_material/tree/main/code . Commented Dec 29, 2021 at 10:03

1 Answer 1

Reset to default
2

For posterity: the algorithm to which Ivan refers is to sort K, then solve the problem recursively as follows. Use QuickSelect to find the ki-th smallest element x where i is ceil(r/2), then recurse on the smaller halves of K and S, and the larger halves of K and S, splitting K about i and S about x.

Finding algorithms that work in the presence of degeneracy (here, equal elements) is often not a high priority for authors of theoretical works, because it makes the presentation of the common case more difficult and doesn't often play a role in determining the computational complexity of the problem. This is essentially a one-dimensional problem, and the black box solution is easy; replace the i-th element of the input yi by (yi, i) and break ties in the comparisons using the second component.

In practice, we can do better. Instead of recursing on {y : y in S, y < x} and {y : y in S, y > x}, use a three-way partitioning algorithm about x (see, e.g., every sufficiently complete treatment of QuickSort), then divide the array S by index instead of value.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks, replacing yi by (yi, i) and using the indexes on comparison worked like a charm

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.