Example object array:

[{
    id: 'a',
    beforeId: null
}, {
    id: 'b',
    beforeId: 'c'
}, {
    id: 'c',
    beforeId: 'a'
}, {
    id: 'd',
    beforeId: 'b'
}]

Output order: d-b-c-a; each element sorted relative to each other element based on its beforeId property.

I could make a temporary array and sort the above array. Is sorting possible with array.sort?

Example object array:

[{
    id: 'a',
    beforeId: null
}, {
    id: 'b',
    beforeId: 'c'
}, {
    id: 'c',
    beforeId: 'a'
}, {
    id: 'd',
    beforeId: 'b'
}]

Output order: d-b-c-a; each element sorted relative to each other element based on its beforeId property.

I could make a temporary array and sort the above array. Is sorting possible with array.sort?

• javascript
• sorting

• @deceze - You could simply do something like: array.sort((a, b) => a.val < b.val) – scagood Commented Feb 16, 2018 at 9:55
• 2 @scagood Nope. 1) The callback is supposed to return <0, 0 or >0, not a boolean. 2) That's not the criterion here. (I admit you'll have to do a double take to see it, but this question isn't half bad.) – deceze ♦ Commented Feb 16, 2018 at 9:56
• 1 A regular sorting function if of no use here because by examining the first two items there is no way to tell their order. Each item is linked only to its immediate neighbours but sorting does not work this way. – axiac Commented Feb 16, 2018 at 10:04
• 2 @scagood I've tried to make it more obvious… it's literally in the name: before id. – deceze ♦ Commented Feb 16, 2018 at 10:05
• 1 Looks like you have a "directed acyclic graph". – T Tse Commented Feb 16, 2018 at 10:24

4 Answers 4

You could build an object with the relations and generate the result by using the object with beforeId: null and unshift all objects for the result array.

The next object is the one with the actual val as key.

Complexity: O(2n).

function chain(array) {
    var o = {}, pointer = null, result = [];

    array.forEach(a => o[a.beforeId] = a);

    while (o[pointer]) {
        result.unshift(o[pointer]);
        pointer = o[pointer].val;
    }

    return result;
}

var data = [{ val: 'a', beforeId: null }, { val: 'b', beforeId: 'c' }, { val: 'c', beforeId: 'a' }, { val: 'd', beforeId: 'b' }];

console.log(chain(data));

.as-console-wrapper { max-height: 100% !important; top: 0; }

This is a terribly inefficient and naïve algorithm, but it works:

const array = [
    {id: 'a', beforeId: null},
    {id: 'b', beforeId: 'c'},
    {id: 'c', beforeId: 'a'},
    {id: 'd', beforeId: 'b'}
];

// find the last element
const result = [array.find(i => i.beforeId === null)];

while (result.length < array.length) {
    // find the element before the first element and prepend it
    result.unshift(array.find(i => i.beforeId == result[0].id));
}

console.log(result);

Is sorting possible with array.sort?

sure, with a helper function:

graph = [
    {id: 'a', beforeId: null},
    {id: 'b', beforeId: 'c'},
    {id: 'c', beforeId: 'a'},
    {id: 'd', beforeId: 'b'}
];

let isBefore = (x, y) => {
    for (let {id, beforeId} of graph) {
        if (id === x)
            return (beforeId === y) || isBefore(beforeId, y);
    }
    return false;
};

graph.sort((x, y) => x === y ? 0 : (isBefore(x.id, y.id) ? -1 : +1))

console.log(graph);

isBefore returns true if x is before y immediately or transitively.

For generic, non-linear topological sorting see https://en.wikipedia/wiki/Topological_sorting#Algorithms

UPD: As seen here, this turned out to be horribly inefficient, because sort involves many unnecessary parisons. Here's the fastest (so far) version:

function sort(array) {
    let o = {}, res = [], len = array.length;

    for (let i = 0; i < len; i++)
        o[array[i].beforeId] = array[i];

    for (let i = len - 1, p = null; i >= 0; i--) {
        res[i] = o[p];
        p = o[p].id;
    }

    return res;
}

which is the @Nina's idea, optimized for speed.

You may try this approach :

// order(null, vals, []) = ["d", "b", "c", "a"]
function order(beforeId, vals, result){
    var id = beforeId || null;

    var before = vals.filter(function(val){
                return val.beforeId ===  id
    });

    if (before.length === 0) return result;   

    return order(before[0].val,
                    vals, 
                [before[0].val].concat(result));
}