CODEWITHSUNDEEP
c++sorting
Rotartsi
Rotartsi

Reputation: 567

Sorting elements into "bins" C++

Hello I've been wondering what was the most efficient way to sort elements into "bins" in c++.

For example, we might have 3 bins:

I want to be able to put an integer into the correct bin based on the range the bin accepts. If the int falls into the range of multiple bins, put it into the bin that is the least full. Finally, I want to be able to tell if the integer doesn't fit into any bin.

What is the most efficient way to do this?

Upvotes: 0

Views: 528

Answers (1)

Thomas
Thomas

Reputation: 182000

It depends.

If the number of bins is small, a simple linear search is usually plenty efficient. Especially if you take into consideration the programmer's time.

If the set of integers is small and the bins don't often overlap, it can be done in constant time. We create a vector indexed by the integer, with as value another vector of (pointers to) the bins. So you can look up the list of applicable bins in constant time. You still need to loop through the applicable bins to find out which is the least full, so this is only constant time if the maximum number of overlapping bins is bounded by a constant.

If the set of integers is large but the bins themselves are relatively small, we can do something similar, but using a hash table instead of a vector.

If we can't make any assumptions, then an interval tree is probably the best solution. But its worst-case behaviour is still linear in the number of bins, because the bins might all overlap and would all need to be checked to find the one that is least full.

Upvotes: 2

Related Questions