I have a list of n items. I need to find the items that will be present in a given range, if the list were to be sorted. Sorting the entire list is not required and not desired, the buckets can be evenly spaced, but if an approach can handle a particular bucket starting at index i and ending at index j it would be preferred.

The ultimate goal is to have a sorted subset starting from index i and ending at index j. Though for the above problem sorting isn't required.


i := 2
j := 4
a := [9,0,1,8,2,7,3,6,4,5]
b := selectBucket(a, i, j)

[2,3] // b
[3,2] // also could work

I found an answer about dividing a list into k buckets, this approach is alright, but if there is a better way to get only a single bucket it would be preferred (that is of course faster).

  • $\begingroup$ What buckets? Your third sentence introduces the notion of buckets out of nowhere. What are the buckets, where do they come from, how are they defined? I'm a bit confused.... $\endgroup$ – D.W. Mar 24 '15 at 5:00

You should use the Quick Select algorithm. I will spare you the details and let you look up the algorithm on your own if you do not know it, but quick select roughly does the following:

Given a list A of size n and and index i, the algorithm will return the ith smallest element of A. Additionally, A will be such that this ith element is in index i, all element earlier in the array are less than or equal to this element, and all later element are greater than or equal to this element. And it does this in O(n) time!

So, just use this algorithm twice on the two indices (you will need to restrict which part of the array you are using for the second query and change the index appropriately, but you can work this out), and you will get what you want! Hope that helps.

Here is a link to the Quickselect Wikipedia article (I have not read it to verify its accuracy): http://en.wikipedia.org/wiki/Quickselect

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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