Need help with algorithm for sorting list

Question

The answer is probably obvious but not to me at this moment, so I was wondering if somebody who is better with sorting algorithms can help lead me in the right direction. This is not homework, I am legitimately trying to work within an existing design for something work related.

Essentially I start with an unordered list of data objects that represent something similar to forum comments. These objects MAY explicitly have one and only one direct parent. In other words

Parent (1...*) ----------- (1...1) Child

A child has a reference to its parent, however a parent cannot see its children (explicitly).

Typically when sorting a list one would pass a comparator which given any two data objects in the collection should return an integer number that represents the distance between the two objects in a graph. The distance between two completely unrelated comments will be based on the Timestamp value of the data object.

The issue is that any two data objects can and should only be compared by timestamp with other data objects from the same parent branch. Here is an example:

DO1 - Time(1000ms)

|___DO3 - Time(5000ms)

DO2 - Time(2000ms)

DO1 and DO2 compared will result in a negative number so those two are sorted correctly relative to each other. DO3 to DO1 is likewise correct because I can assume that any branch above a comment must be less than. The problem comes with comparing DO3 to DO2. I thought that I should compare the highest order parent to DO2 in this case and that works until there are DO children under DO3.

I am trying to figure out if the current object graph is even enough information for a comparator to correctly return an appropriate number for any two comparisons. Perhaps the comparator needs to be initialized with the unordered list first so that it can build a tree structure where I can see a list of children from any given parent explicitly? Or perhaps I need to refactor? At this stage I am not concerned about performance. Thank you.

Answer 1

The obvious approach is to walk the tree depth first, taking children of each node in order of their timestamp. That is the order you want.

Building the tree and than iterating it will obviously save you time, but you can just take all entries with given parent pointer while testing.

Alternatively you could define the ordering so that descendants come after their predecessors and other nodes are ordered by timestam of immediate children of their common ancestor. So:

ROOT
 +- DO1 T=1
 |   +- DO2 T=5
 |   +- DO3 T=8
 |       +- DO4 T=12
 +- DO5 T=3
     +- DO6 T=11

DO2 > DO1 because it's a descendant, DO4 >DO1because it's also descendant,DO3>DO2because they are both immediate children to their ancestorDO1andDO3has higher timestamp andDO6>DO4because their ancestor isROOTto which you come fromDO6viaDO5and fromDO4viaDO1andDO5has higher timestamp thanDO1`.

But building and walking the tree is going to be faster.