Sort an array by its relative position

Question

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?

Answer 1

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);

Answer 2

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.org/wiki/Topological_sorting#Algorithms

UPD: As seen here, this turned out to be horribly inefficient, because sort involves many unnecessary comparisons. 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.

Answer 3

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