Modifying selection algorithm to select weighted items

Question

Hi guys, I am attempting to modify the selection algorithm to work with the following situation:

My imput is a list of numbers x1, x2, ... , xn (not necessarily ordered).

Each of these numbers has a weight "w". I call W the sum of all the weights.

If I provide a value X, which is greater than 0 but no larger than W, how can I find a xi, such that the sum of the weights of all x's with index greater than i is less than X, and xi's weight + sum of the weights of all items with index greater than i is greater than or equal to X.

This is easily accomplished if we sort all the x's according to their index, but I wish to do that without sorting.

Answer 1

You should not have to sort them if you are given the identifier i. It sounds like you want them in order of their identifiers, which are known, so you just have to make one pass through the list O(n) to put them in order. Then follow one of the posted solutions to figure out the proper value of i. Am I misunderstanding the problem?

Update

So lets say you have four values, the identifiers are like this:

[ x4, x1, x3, x2 ]

And their weights respectively are:

[ 14, 10, 5, 19 ]

All you have to do is first get the lists in order. It is not the same as sorting it because in this cause you have x1 .. xn, where the numbers are all contiguous with no repeats etc. So you know the result will be a new list of size 4.

Make one pass through the first list. In this case the first number has an identifier of 4, so put that in the new list at position 4, and put the first weight in a new weight list also at position 4. Next will be put in position 1, so on and so fourth.

After this one pass, your lists will look like:

[ x1, x2, x3, x4 ] and [ 10, 19, 5, 14]

So you now have the order you want. It becomes easy at this point to just start at the end of the weight list and find the property you are looking for with at most one more traversal of the list.

Thus it should be O(n).