CODEWITHSUNDEEP
sortingintegerrange
user2694476
user2694476

Reputation: 51

Need unusual sorting algorithm

I have a list of approximately 5000 integer ranges (e.g. 30-50, 45-100, etc.) that I need to put into a "sorted order." This order needs to be based on which list items are range subsets of other items. For example 10-12 would be a range subset of 2-14. If list(1).low_value >= list(2).low_value and list(1).upper_value <= list(2).upper_value then list(1) is a subset of list(2). To complicate things, some list items will be subsets of many list items.

I ultimately need to create an ordered list such that list items at lower indexes are always subsets of, or unrelated (e.g. ranges 1-2 and 3-4) to, any items following it in the list.

Thanks, Mark

Upvotes: 3

Views: 188

Answers (1)

Mechanical snail
Mechanical snail

Reputation: 30647

My first reaction was that it sounds like a topological sort, where ranges are viewed as nodes in a graph, and an edge is considered to exist from range A to range B iff A is a subrange of B.

I assume you mean that the condition for the output list is that if A appears before B, then B is not a strict subset of A (but it's fine if A = B, A and B are disjoint, or A and B overlap without one being a subrange of the other).

If the width of range B (B.upper_value - B.low_value) is at least that of range A, then B cannot be a strict subrange of A. Hence it suffices to sort the list by increasing width of the ranges. This can be done in linear time (assuming fixed-size integers) by computing the widths and then doing a radix sort.

Upvotes: 1

Related Questions