Get Even More Visitors To Your Blog, Upgrade To A Business Listing >>

Sorting a multi-dimensional object with hierarchical groups in Javascript (Node.js)

Tags: object sort kid

Sorting a multi-dimensional object with hierarchical groups in Javascript (Node.js)


I have an hierarchical Object on which I sort children by walking over the parents and sort the children. This works. But now, I need to optionally break the hierarchy and create new virtual restraints.

In order to illustrate this, let's take an example of a Man, who has x Wifes. With each wife, he has y Kids. I can sort kids per wife, or wifes per man.

Man01   Wife01a     Kid01aA
        Wife01b     Kid01bC
Man02   Wife02c     Kid02cE
        Wife02d     Kid02dG

Let's just give them names:

Murphy  Winnie  Kurt
        Wendy   Klaus
Marley  Wonda   Kasper
        Wilma   Kevin

And think about sorting them alphabetically within their parents:

Marley  Wilma   Karla
        Wonda   Kasper
Murphy  Wendy   Klaus
        Winnie  Kara

But now, we want to be able to sort the kids that belong to a man, or wifes in general, or kids in general?

Marley  Wilma   Karla
        Wonda   Kasper
        Wilma   Kevin
        Wonda   Kyra
Murphy  Winnie  Kara
        Wendy   Klaus
        Wendy   Klea
        Winnie  Kurt

This is an immensly simplified fictional object. In reality, in stead of sorting alphabetically, I do a multi-column-sort over many many properties.

It's fine to output the results to a table, but processing itself already takes a lot of time and memory. I don't want to complicate that further.

If that was no issue, I would just flatten the object as a table in an array, chain every multi-column sort into a super multi-column sort, and regroup starting at the closest common ancestor that was left intact with loops.

But I am trying to solve this in a more efficient way, without converting the object to a full-blown table-array.

  • How do I tacle this? actually looping over each and every one of them twice?
    • Perhaps there is a 'well-known' solution for this kind of sorting that I just don't know about yet?
    • Maybe there is wizardry available creating table-like records using references for all 'virtual' parents, grouping these references back into hierarchy afterwards without looping over them?

Here's an example of the kind of Object I am referring to: By Object, I mean, quite literally {}, although the object contains arrays [] of objects {} when it has multiple members.

    "men"   : [
            "name"  : "Murphy",
            // a lot of properties
            "wifes" : [
                    "name"  : "Winnie",
                    // a lot of properties
                    "kids"  : [
                            "name"  : "Kurt",
                            // a lot of properties
                        }, {}, {} // etc...
                }, {}, {} // etc...
        }, {}, {} // etc...

Note that in this case my example is wrong, because Man, Wife and Kid are all humans. But in reality there are different object with dissimilar properties. I should have chosen Universe, Planet, Soil or something, assuming there are multiple universes. ;)

Problem courtesy of: Redsandro


we want to be able to sort the kids that belong to a man

Then I would arrange them like this:

Marley  Karla   Wilma   
        Kasper  Wonda
        Kevin   Wilma
        Kyra    Wonda
Murphy  Kara    Winnie
        Klaus   Wendy
        Klea    Wendy
        Kurt    Winnie

Of course, since there is only one mother per child there is no much difference, but for your actual data this might be different.

Yet, you can already see now that you just have to sort each of the kids arrays per man.

So, in general, instead of flattening to a large table array, multi-column sorting that, and regrouping the results as you suggested, you should do the grouping first and sort the groups afterwards - a bit like a bucket sort.

var men = data["men"];
men.forEach(function (man) {
    var kids = {};
    var wifes = man["wifes"];
    for (var i=0; i
    // });

    // you might integrate this loop in the above, but it's independent:
    man["kids"].forEach(function(kid) {
        kid["mothers"].sort( /* some mother comparison */ );
// now every man has a sorted "kids" array with each kid having a sorted "mothers" array
Solution courtesy of: Bergi


View additional discussion.

This post first appeared on Node.js Recipes, please read the originial post: here

Share the post

Sorting a multi-dimensional object with hierarchical groups in Javascript (Node.js)


Subscribe to Node.js Recipes

Get updates delivered right to your inbox!

Thank you for your subscription