I have a list of n items. I need to find the items that will be present in a giv

Question

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.

Example:

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

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.