# a funky interleaved sorting problem

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 `nil`s 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 ).

• "Geek" is not a term of endearment. It is a circus performer that bites the heads off of chickens. – Robert Harvey May 4 '16 at 14:46
• @RobertHarvey maybe not in your social circles but in the US "geek" is typically used as a very common and non-perjorative term for someone who works with computers, typically a programmer. It is uncommon to find anyone who is aware of the original meaning, nevermind assumes its usage. – masukomi May 4 '16 at 14:57
• @masukomi Also, are you sure your problem statement is accurate? In particular, should `[nil, 7]` really sort before `[6, 8]`? – Marnen Laibow-Koser May 4 '16 at 15:03
• @RobertHarvey I do agree with you that beginning "I need your help geeks" is inappropriate on StackExchange, but that's because the whole sentence is unnecessary, not because of the word "geek". – Marnen Laibow-Koser May 4 '16 at 15:12
• As I just said, it's not about the word definition, nor did I say it was in my clarifying comment. – Robert Harvey May 4 '16 at 15:13

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.
• I thought of this too, but notice that it's not quite the sorted order that was requested. – Marnen Laibow-Koser May 4 '16 at 15:25
• yup, almost, but not quite `[2, nil], [3, nil], [nil, 3]` don't match the desired output – masukomi May 4 '16 at 15:26
• @masukomi so you'd want `[nil, x]` to go before `[x, nil]`? – Dennis Krupenik May 4 '16 at 15:28
• Programmers is about conceptual questions and answers are expected to explain things. Throwing code dumps instead of explanation is like copying code from IDE to whiteboard: it may look familiar and even sometimes be understandable, but it feels weird... just weird. Whiteboard doesn't have compiler – gnat May 4 '16 at 16:06
• @gnat thank you for the input, I've tried to add a human-readable explanation of the code, as well as an extended version of it – Dennis Krupenik May 4 '16 at 19:46

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

• ...and there's the rub. The problem (IMHO) is largely that writing a comparator function for this is rather difficult. – Marnen Laibow-Koser May 4 '16 at 15:27
• Yes, one needs to be able to define it in human language. In other words, it needs a domain-specific definition. With that, it ought to be trivial to code up. Defining the domain specific definition by giving a few examples is not very rigorous. So, I'd assert we can only point in the right direction here, as the domain definition of collation ordering is incomplete in the question. – Erik Eidt May 4 '16 at 15:30

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?

``````# 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) }
``````
• Programmers is about conceptual questions and answers are expected to explain things. Throwing code dumps instead of explanation is like copying code from IDE to whiteboard: it may look familiar and even sometimes be understandable, but it feels weird... just weird. Whiteboard doesn't have compiler – gnat May 5 '16 at 4:17