6
\$\begingroup\$

I have an array of nested objects:

[
    {_id:1, parent:0, name:'Z'},
    {_id:4, parent:0, name:'A'},
    {_id:2, parent:1, name:'H'},    
    {_id:8, parent:2, name:'G'},        
    {_id:5, parent:4, name:'M'},
    {_id:6, parent:4, name:'N'},
    {_id:3, parent:1, name:'Z'},
    {_id:7, parent:2, name:'L'}
]

I need to sort them in the way for nodes at same level will be sorted by alphabetic order (asc/desc configurable) and all child nodes should be after their parent and before their parent's sibling node also sorted by alphabetic order.

For example, if sorted by asc, the output should be

[ 
    { _id: 4, parent: 0, name: 'A' },
    { _id: 5, parent: 4, name: 'M' },
    { _id: 6, parent: 4, name: 'N' },
    { _id: 1, parent: 0, name: 'Z' },
    { _id: 2, parent: 1, name: 'H' },
    { _id: 8, parent: 2, name: 'G' },
    { _id: 7, parent: 2, name: 'L' },
    { _id: 3, parent: 1, name: 'Z' } 
]

In the output, 4 is before 1 because A < Z. 5 and 6 are sorted alphabetically under 4 and before 1. Similar case for 8 and 7 under 2 and before 3.

and if desc, the output should be:

[ 
    { _id: 1, parent: 0, name: 'Z' },
    { _id: 3, parent: 1, name: 'Z' },
    { _id: 2, parent: 1, name: 'H' },
    { _id: 7, parent: 2, name: 'L' },
    { _id: 8, parent: 2, name: 'G' },
    { _id: 4, parent: 0, name: 'A' },
    { _id: 6, parent: 4, name: 'N' },
    { _id: 5, parent: 4, name: 'M' }
]

I tried to implement a function as below.

function sortByHierarchyAndName(arr, sort) {
    var i = 0; 
        j = 0;
        t = 0; 
        parentFound = false; 
        x = arr.length;
        arr2 = []; 

    //Sort by parent asc first 
    arr = arr.sort(function(a, b) {
        if(a.parent < b.parent) return -1; 
        if(a.parent > b.parent) return 1; 
        return 0; 
    }); 

    for(; i < x; i += 1) {
        t = arr2.length;
        if(t === 0)  arr2.push(arr[i]);
        else if(arr[i].parent === 0) {
            for(j = 0; j < t; j += 1) {
                if(sort === -1) {
                    if(arr[i].name >= arr2[j].name) arr2.splice(j, 0, arr[i]);
                } else {
                    if(arr[i].name <= arr2[j].name) arr2.splice(j, 0, arr[i]);
                }
            }
            if(arr2.length === t) arr2.push(arr[i]);
        }
        else {
            parentFound = false;
            for(j = 0; j < t; j += 1) {
                if(arr[i].parent === arr2[j]._id) {
                    if(j === t - 1) {
                        arr2.push(arr[i]); 
                    }
                    parentFound = true; 
                } else if(arr[i].parent === arr2[j].parent) {
                    if(sort === -1) {
                        if(j === t - 1) arr2.push(arr[i]); 
                        else if(arr[i].name >= arr2[j].name) {
                            arr2.splice(j, 0, arr[i]);
                            j = t; 
                        }
                    } else {
                        if(j === t - 1) arr2.push(arr[i]); 
                        else if(arr[i].name <= arr2[j].name) {
                            arr2.splice(j, 0, arr[i]);
                            j = t; 
                        }
                    }
                } else if(arr[i].parent > arr2[j].parent && parentFound) {
                    arr2.splice(j, 0, arr[i]);
                    j = t; 
                }
            }
        }
    }
    return arr2; 
}

Assuming array.sort() take f(n) amount of time when sorting by parent asc for an array of length n, I'm doing some performance analysis for the implementation as below.

Best case: \$f(n) + x \times n + y \times \sum (\frac{1...n}{2})\times n\$

Worst case: \$f(n) + x \times n + y \times \sum (1...n)\times n\$

x - factor in processing any given element in arr.

y - factor in processing any given element in arr against any element in arr2.

As you can see, in both case, the duration of execution will grow exponentially as n grows, so I'm wondering if I can do something to improve this.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review. As a courtesy to other users, please declare your cross-post. \$\endgroup\$ – 200_success Feb 11 '16 at 3:32
  • \$\begingroup\$ These added notes don't really belong in the question itself. Upvoting and accepting good answers is enough. \$\endgroup\$ – Jamal Feb 12 '16 at 2:10
  • \$\begingroup\$ This is a very strict community! :D Anyway, I do that for the benefits of people who comes in later, so that they can see the summary of all good points from all replies in one glance. I know it's not a current practice, but isn't it a good practice? \$\endgroup\$ – Lee Feb 12 '16 at 2:14
  • 1
    \$\begingroup\$ @Lee, The problem is that if you add summary points it kind of changes both your question and the answers. Possibly invalidating answers. It is better that you accept one of the answers, and let the up- and down-votes on answers reflect good valid points related to your question! So, the practice is there for a reason, and it does work nicely as is! :-) \$\endgroup\$ – holroy Feb 12 '16 at 2:25
4
\$\begingroup\$

Reverse engineering

It looks to me like the function builds the result array by doing some kind of insertion sort. That's a very impressive solution, but unfortunately, it's unreadable.

To start with, the initialization block…

var i = 0; 
    j = 0;
    t = 0; 
    parentFound = false; 
    x = arr.length;
    arr2 = [];

… is all clutter. Nobody likes to read that, especially when there is no indication what these variables all mean. A much better way would be to write the outermost loop as for (var i = 0; i < arr.length; i++) { … }, which immediately removes i and t from that block. Similarly, j and t can be eliminated.

The insertion sorts are rather nasty, because you have the ascending and descending cases, as well as the last-element case. You also have to be careful not to stray into another parent node's children.

Alternate solution

You would be much better off building the tree, such that each node's children are in a separate array. Then you can use standard sorting procedures and traditional tree-traversal techniques.

I would rename the function to depthFirstTreeSort() to be more precise. To make it feel more like JavaScript's Array.sort(), I would have it take a comparator function, and write the sorted result in place. The comparator can use String.localeCompare().

I recommend breaking down the steps into helper functions, each with its own documentation and local variables for ease of understanding. The depthFirstTraversal() function is essential since it's recursive. It uses the Visitor pattern.

function depthFirstTreeSort(arr, cmp) {
    // Returns an object, where each key is a node number, and its value
    // is an array of child nodes.
    function makeTree(arr) {
        var tree = {};
        for (var i = 0; i < arr.length; i++) {
            if (!tree[arr[i].parent]) tree[arr[i].parent] = [];
            tree[arr[i].parent].push(arr[i]);
        }
        return tree;
    }

    // For each node in the tree, starting at the given id and proceeding
    // depth-first (pre-order), sort the child nodes based on cmp, and
    // call the callback with each child node.
    function depthFirstTraversal(tree, id, cmp, callback) {
        var children = tree[id];
        if (children) {
            children.sort(cmp);
            for (var i = 0; i < children.length; i++) {
                callback(children[i]);
                depthFirstTraversal(tree, children[i]._id, cmp, callback);
            }
        }
    }

    // Overwrite arr with the reordered result
    var i = 0;
    depthFirstTraversal(makeTree(arr), 0, cmp, function(node) {
        arr[i++] = node;
    });
}


var data = [
    {_id:1, parent:0, name:'Z'},
    {_id:4, parent:0, name:'A'},
    {_id:2, parent:1, name:'H'},
    {_id:8, parent:2, name:'G'},
    {_id:5, parent:4, name:'M'},
    {_id:6, parent:4, name:'N'},
    {_id:3, parent:1, name:'Z'},
    {_id:7, parent:2, name:'L'}
];

function nameCmp(a, b) { return a.name.localeCompare(b.name); }
depthFirstTreeSort(data, nameCmp);  // ascending sort
depthFirstTreeSort(data, function(a, b) { return nameCmp(b, a); });  // descending sort
\$\endgroup\$
4
\$\begingroup\$

Since you have a representation of a tree i suggest using it, then traverse it in pre-order

So if

[
    {_id:1, parent:0, name:'Z'},
    {_id:4, parent:0, name:'A'},
    {_id:2, parent:1, name:'H'},    
    {_id:8, parent:2, name:'G'},        
    {_id:5, parent:4, name:'M'},
    {_id:6, parent:4, name:'N'},
    {_id:3, parent:1, name:'Z'},
    {_id:7, parent:2, name:'L'}
]

lets build a tree like this

   [
      {_id:1, parent:0, name:'Z', children: 
         [
             {_id:2, parent:1, name:'H', children: 
                [
                   {_id:8, parent:2, name:'G', children: []},
                   {_id:7, parent:2, name:'L', children: []}
                ]
             },
             {_id:3, parent:1, name:'Z', children: []}
         ]
      },
      {_id:4, parent:0, name:'A', children: 
         [
             {_id:5, parent:4, name:'M', children: []},
             {_id:6, parent:4, name:'N', children: []}
         ]},
   ]

my suggestion is like this:

var nodes = [
    {_id:1, parent:0, name:'Z'},
    {_id:4, parent:0, name:'A'},
    {_id:2, parent:1, name:'H'},    
    {_id:8, parent:2, name:'G'},        
    {_id:5, parent:4, name:'M'},
    {_id:6, parent:4, name:'N'},
    {_id:3, parent:1, name:'Z'},
    {_id:7, parent:2, name:'L'}
]
var tree = {_id:0};



var addChildrenToNode = function(node,cmp){
    var currentNodeId = node._id;
    node.children = [];
    nodes.forEach(function(e){
        if(e.parent === currentNodeId){
            e = addChildrenToNode(e);
            node.children.push(e);
        }
    });
    node.children = node.children.sort(cmp); // sort the children
    return node;
};

var cmp = function(a, b) { 
    if(a.name < b.name) return -1; 
    if(a.name > b.name) return 1; 
    return 0; 
};
tree = addChildrenToNode(tree,cmp);

Then you only have to do the pre-order traverse, like this:

var preOrderTraverse = function(node, fn){ // sends values of tree to fn in pre-order
    fn(node); //call at preorder
    if(node.children.length > 0){
        node.children.forEach(function(e){
            preOrderTraverse(e,fn);
        });
    }
}

preOrderTraverse(tree,
    function(node){ // do what you like with each node
        console.log(node);
    }
);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.