andlrc - 2 years ago 52
Javascript Question

Sorting array recursive

I have an array like this:

``````var a = [
{id: 1, pid: 0},
{id: 2, pid: 1},
{id: 3, pid: 1},
{id: 4, pid: 2},
{id: 5, pid: 2},
{id: 6, pid: 3},
{id: 7, pid: 3}
]
``````

And a map object like this:

``````var map = {
"1": {id: 1, pid: 0},
"2": {id: 2, pid: 1},
"3": {id: 3, pid: 1},
"4": {id: 4, pid: 2},
"5": {id: 5, pid: 2},
"6": {id: 6, pid: 3},
"7": {id: 7, pid: 3}
}
``````

I am trying to sort it to match this pattern:

``````var result = [
{"id": 1, "pid": 0},
{"id": 2, "pid": 1},
{"id": 4, "pid": 2},
{"id": 5, "pid": 2},
{"id": 3, "pid": 1},
{"id": 6, "pid": 3},
{"id": 7, "pid": 3}
]
``````

As you can see this is a nested tree structure. And I want to get
`pid`
under the matching
`id`
and the lowest
`id`
at the top.

Is there any way to sort an array like this using only one iteration? - if not, it would be nice to see an example on how to get around it.

So far I only have:

``````a.sort(function(q, w) { return q.pid - w.pid; });
``````

And I'm thinking of using my map to find my parent using
`pid`
->
`id`
and then sort on that key. It's okay to store extra properties on my objects as well.

Assuming that there is a single root with pid 0:

``````var children = {}
var root = null;
a.forEach(function(e) {
children[e.id] = [];
});

a.forEach(function(e) {
if (e.pid === 0) {
root = e;
}
else {
children[e.pid].push(e);
}
});

var sorted = [];

function preorder(e) {
sorted.push(e);
if (children.hasOwnProperty(e.id)) {
children[e.id].forEach(preorder);
}
}
preorder(root);
``````

Result:

``````[
{"id":1,"pid":0},
{"id":2,"pid":1},
{"id":4,"pid":2},
{"id":5,"pid":2},
{"id":3,"pid":1},
{"id":6,"pid":3},
{"id":7,"pid":3}
]
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download