a funky interleaved sorting problem

Question

I have an array of items. Some items have a number on both sides. I'll call these "matched pairs". I need to sort the items between the matched pairs in a particular way.

There's a "from number" and a "to number" There may be more from -> nil than nil-> to, or vice-versa. There may also be NO items between the matched pairs.

You can assume that the numbers will always be sorted within their column. E.g. From numbers will go from 1 to x ascending, and to numbers will go from 1 to x ascending. There may be nils inserted along the way though.

# I have this
#   v from number
#          v to number
[
    [nil,  1],
    [1,    2],  # a matched pair
    [2,    nil],
    [3,    nil],
    [4,    nil],
    [5,    nil],
    [nil,  3], # note that there are more 
    [nil,  4], # nil -> to number than 
    [nil,  5], # from number -> nil
    [nil,  6],
    [nil,  7], 
    [6,    8],  # another matched pair
    [7,    9],  # nothing in between
    [8,    nil],# no nil->to number to pair it with
    [9,    10]
]

I need to transform it to this. We're almost, but not quite interleaving the items from each column.

[
    [nil,  1],
    [1,    2],
    [2,    nil],
    [nil,  3],
    [3,    nil],
    [nil,  4],
    [4,    nil],
    [nil,  5],
    [5,    nil],
    [nil,  6],
    [nil,  7],
    [6,    8],
    [7,    9],
    [8,    nil],
    [9,    10]
]

Additional Information that may, or may not, be useful

These numbers represent lines in two documents. In the example above, the text on line 2 in the "from" document was not found in the "to" document. It has been replaced by the text on line 3 ( in the "to" document ). The text on line 3 in the "to" document wasn't found in the "from" document so. So, 2 -> nil (two went away) nil->3 ( three was added ).

Answer 1

To guarantee ascending order in both columns we can compare by column when there is no nil and by max value when there is:

.sort { |(a0, a1), (b0, b1)|
  if [a0, b0].none?(&:nil?)
    a0 <=> b0
  elsif [a1, b1].none?(&:nil?)
    a1 <=> b1
  else
    a0, a1, b0, b1 = [a0, a1, b0, b1].map(&:to_i)
    [[a0, a1].max, a0, a1] <=> [[b0, b1].max, b0, b1]
  end
}

1. Compare two items at a time
2. If the left columns are both positive integers then use that to sort.
   • this works because if they both have numbers then the right number is always correct relative to the left, so sorting on the left gets you the right result.
3. If the right columns are both positive integers then use that to sort.
   • we know it's not a matched pair and both left numbers are nil and both rights are comparable so...
4. Convert all the nils to something we can work with (.to_i makes them zero).
5. Otherwise, create arrays to sort, with the 1st element of each array being the non-null (non-zero at this point) number. .max is just an easy way of getting the non-zero one.

Answer 2

Most languages allow a custom comparator function to be supplied to the sort. See Java Comparator

One use of a custom comparator, for example, is to sort based on two attributes (a primary an secondary) with one sort. A comparator for this will first compare the primary attributes, then only if they are equal, will check the secondary attribute.

A custom comparator for your sort would first obtain a primary value for each of the two items being compared. This primary value would be either the first number of the range, or if nil the last number of the range. Then if the primary values are equal, the comparator would move on to test a secondary value, similarly obtained from the last range with an appropriate behavior when nil (e.g. max value or something).

Answer 3

Ah...I think I may have an answer. Here's a two-pass approach (calling each pair [x, y]).

1. Select all pairs where x is not nil. Sort them by x. Call the resulting list s.
2. Select all pairs where x is nil. Insert them into s at the appropriate places (I'm not sure how you determine the appropriate places, though).

Does that help?

Answer 4

# ruby syntax

 def compare_them (obj1, obj2)
  if obj1[0].nil? 
    if !obj2[0].nil?
      return obj1[1] <=> obj2[0]
    else  
      if obj2[1].nil?
        if obj1[1] == obj2[0]
          return -1
        else 
          return obj1[1] <=> obj2[0]
        end
      else
        return obj1[1] <=> obj2[1]
      end
    end
  else
    if obj2[0].nil?
      if obj1[1].nil?
        if obj1[0] == obj2[1]
          return 1
        else 
          return obj1[0] <=> obj2[1]
        end
      else
        return obj1[1] <=> obj2[1]
      end
    else
      return obj1[0] <=> obj2[0]  
    end
  end
end

foo = [[nil, 1],
       [1, 2],
       [2, nil],
       [3, nil],
       [4, nil],
       [5, nil],
       [nil, 3],
       [nil, 4],
       [nil, 5],
       [nil, 6],
       [nil, 7],
       [6, 8],
       [7, 9],
       [8, nil],
       [9, 10]]

foo.sort { |a1,a2| compare_them(a1, a2) }