Sorting an array of objects with specific exceptions in Javascript

Question

I've got an array of objects where some of the elements are clones of another, hence they have a property that references another property of the original (simplified example):

var a = [{
    id: 'x0',
    name: 'Foo',
    isClone: false,
    wasCloned: true,
    originalId: ''
}, {
    id: 'y1',
    name: 'Bar'.
    isClone: false,
    wasCloned: false,
    originalId: ''
}, {
    id: 'z2',
    name: 'Foo',
    isClone: true,
    wasCloned: false,
    originalId: 'x0'
}];

In this example, the third element references the id of the first - which makes it a clone in that sense. Unfortunately, the id's are not incremental/chronological and can basically be any random string.

Now, the task at hand is to sort the array in such a fashion so that the clones are always placed on the array position right before the position of its original. If the array element is not a clone, the ordering should proceed as usual. In other words, once sorted, the order in this example would be 2,0,1.

I've tried to figure out how to use Array.sort for this, but can't really wrap my head around it. This is basically what I've got (which doesn't work):

var sortedA = a.sort(function(one, other) {
    var sorted;
    if (one.id == other.originalId) {
        sorted = -1;
    } else {
        sorted = 0;
    }
    return sorted;
});

Any help on this would be much appreciated, thank you.

So you don’t want the order of the original items within that array to change? Then I think “sorting” is not the way to go (because you will have a hard time keeping that order when you “sort” the whole array), but rather building a new array. — CBroe, Mar 20 '15 at 11:34
What about returning `1`? Usually negative (`-1`) floats to top, positive (`+1`) sinks to the bottom, and identical (`0`) stays where it is when sorting. — Mr. Polywhirl, Mar 20 '15 at 11:47
@Mr.Polywhirl: That's not exactly how comparisons work, but indeed not returning `1` [hits a nerve](http://stackoverflow.com/q/24080785/1048572)! — Bergi, Mar 20 '15 at 13:36
@Alnitak good question, forgot to specify that - an item can only be cloned once, and the clones can't be cloned. — Andreas Bohman, Mar 20 '15 at 13:39
@Bergi: But that *is* the generic approach. I was not saying that this is the *only solution*. — Mr. Polywhirl, Mar 20 '15 at 14:42
@Mr.Polywhirl: Meh, your statement just sounded as if you'd assign a number to each item and they were sorted by that. Comparisons need to define an order on all items, and the sorting is only established by repeatedly applying the comparison function. Which always tells us things about two items only, and is not necessarily related to "floating". — Bergi, Mar 20 '15 at 14:54

score 2 · Answer 1 · answered Mar 20 '15 at 11:50

2

You should use the following sorting function:

var sorted = a.sort(
    function (a, b) {
        var compareA = a.originalId || a.id;
        var compareB = b.originalId || b.id;

        if (compareA < compareB) {
            return -1;
        } else if (compareA > compareB) {
            return 1;
        } else {
            return a.originalId !== '' ? -1 : 1;
        }
    }
);

An example of the function working is available here.

answered Mar 20 '15 at 11:50

Phylogenesis

7,775
19
27

+1 for the correct solution, but an explanation would be nice. Notice that you should also [`return 0` for identical values](http://stackoverflow.com/q/20883421/1048572) – Bergi Mar 20 '15 at 13:40
I believe this kind of string comparison won't work unfortunately, since the ids/originalIds are not guaranteed to be chronological... right? Gave me a deeper understanding of what you can do with the sort function though, so thanks! – Andreas Bohman Mar 20 '15 at 13:41
@AndreasBohman: Well, you wanted to sort by the ids, didn't you? – Bergi Mar 20 '15 at 14:51

Pierrickouw · Answer 2 · 2015-03-20T12:12:41.820

Get all the objects with an original ID and save the ones without.

var others = [];
var data = a.filter(function(elem) {
    if (elem.originalID !== '') {
        return true;
    } else {
        others.push(elem); // keep a trace of elements without originalID
        return false;
    }    
});

Sort them so they are all packed together

data.sort(function(a, b) {
    return a.originalID.localeCompare(b.originalID); //compare string
});

You now have all the element with same originalID packed together. We then just need to add the element with the good id at the end of every packed element with the same originalID.

var originId = data[0].originalID; //get the first origin id
for(var i = 0; i < data.length; i++) {
   var elem = data[i];
   //the end of a packed list
   if(originID !== elem.originalID) {
       var val = others.find(function(e, index) { //find the element with the good id
           if(return e.id === originID) {
               others.splice(index, 1);//remove the element from the others array
               return true;
           } else {
               return false;
           }
       });

       data.splice(i, 0, val[0]); //insert it at the end of the packed list
       originID = elem.originalID; //save for next loop
   }
}



//just need to add the remaing element to the list
var final = data.concat(others);
console.log(final);

It sure can be improved (adding checks, doing less work) but I think you got the idea.

score 1 · Accepted Answer · answered Mar 20 '15 at 12:07

My solution is similar to GreenLeaf's. It will create a new array and not modify the original, which could or could not be a problem for you.

The approach is to first remove the clones. Then the array can be sorted if desired, and then finally the clones are inserted above their origin object:

// create a new array without any clones, save the clones 
var clonesMap = {};
var aWithoutClones = a.filter(function(item){
    if (item.isClone) {
        if (!clonesMap[item.originalId]) {
            clonesMap[item.originalId] = [];
        }
        clonesMap[item.originalId].push(item);
        return false;
    }

    return true;
});

// here you can sort aWithoutClones

// put all clones back before their original object
a = [];
for (var i = 0; i < aWithoutClones.length; i++) {
    var currId = aWithoutClones[i].id;
    if (clonesMap[currId]){
        a = a.concat(clonesMap[currId]);
    }
    a.push(aWithoutClones[i]);
}

I think this gives you more flexibility since you now have a chance to sort the array without having to consider the clones. Also, you could also sort the clones with a separate sort function.

Perfect, that does the trick and was the most optimal for me, since it allows me to save only the clones for later use in a convenient way. Many thanks! — Andreas Bohman, Mar 20 '15 at 13:43

Sorting an array of objects with specific exceptions in Javascript

3 Answers3