Sorting array recursive

Question

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.

You're indenting it like it's nested, but you haven't actually nested any arrays or objects. — Barmar
– Barmar, Commented Apr 23, 2013 at 10:12
You can't do that with a simple comparison function that only knows about two elements! — phant0m
– phant0m, Commented Apr 23, 2013 at 10:14
@Barmar I think he's aware of that, basically, he wants to have a tree and then linearize with pre-order. — phant0m
– phant0m, Commented Apr 23, 2013 at 10:15
@Barmar the reason why I'am indenting the result is just for clarity - at least i thought. — Andreas Louv
– Andreas Louv, Commented Apr 23, 2013 at 10:16
sort() looks at each pair of array elements and needs to know which one is higher or lower. But your ordering is based on parent-child relationships between specific elements. — Barmar
– Barmar, Commented Apr 23, 2013 at 10:21

phant0m · Accepted Answer · 2013-04-23 10:26:11Z

2

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}
]

answered Apr 23, 2013 at 10:26

phant0m

17k6 gold badges52 silver badges84 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Sorting array recursive

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related