How can I sort a javascript array of objects that specify prerequisites between them?

Question

I have an array of objects that determine which ones should be showed first. An example of this array would be:

[
    {
        "id": "b94ae1a5-c6b2-4e45-87cd-a4036fdb7870",
        "prerequisites_ids": [
            "2a4fdd9c-45d0-49d9-a0eb-ba5a0464f2b1"
        ]
    },
    {
        "id": "ef7d2415-808f-4efc-939e-2692f38a5ee7",
        "prerequisites_ids": [
            "74e41a2c-e74e-4016-bb2c-f2e84c04fe92"
        ]
    },
    {
        "id": "74e41a2c-e74e-4016-bb2c-f2e84c04fe92",
        "prerequisites_ids": []
    },
    {
        "id": "2a4fdd9c-45d0-49d9-a0eb-ba5a0464f2b1",
        "prerequisites_ids": [
            "ef7d2415-808f-4efc-939e-2692f38a5ee7"
        ]
    }
]

How could I sort it to get this?

[
    {
        "id": "74e41a2c-e74e-4016-bb2c-f2e84c04fe92",
        "prerequisites_ids": []
    },
    {
        "id": "ef7d2415-808f-4efc-939e-2692f38a5ee7",
        "prerequisites_ids": [
            "74e41a2c-e74e-4016-bb2c-f2e84c04fe92"
        ]
    },
    {
        "id": "2a4fdd9c-45d0-49d9-a0eb-ba5a0464f2b1",
        "prerequisites_ids": [
            "ef7d2415-808f-4efc-939e-2692f38a5ee7"
        ]
    },
    {
        "id": "b94ae1a5-c6b2-4e45-87cd-a4036fdb7870",
        "prerequisites_ids": [
            "2a4fdd9c-45d0-49d9-a0eb-ba5a0464f2b1"
        ]
    }
]

I have tried creating a custom function:

export function comparePrerequisites(a, b) {
  if (!a.prerequisites_ids) {
    return -1
  }
  if (a.prerequisites_ids.includes(b.id)) {
    return 1;
  }
}
data.sort(comparePrerequisites)

but does not seem to work. Thanks in advance!

An array, empty or not, is always [truthy](https://developer.mozilla.org/en-US/docs/Glossary/Truthy). You would have to check its `.length` property. — Andreas, Mar 21 '22 at 11:19
If prerequisites are the primary sort key, what's the secondary one? (E.g., what order do you want `a` and `b` to be in when they both have the same prerequisites, or none?) — T.J. Crowder, Mar 21 '22 at 11:19
And what about cycles? Two objects that say they mutually depend on one another? — T.J. Crowder, Mar 21 '22 at 11:27

score 1 · Accepted Answer · answered Mar 21 '22 at 11:32

We have here the requirements for a topological sort. This is not a job for the sort method. Instead you can use recursion (a DFS traversal) to drill down to a dependency that is already collected, or to a leaf (no dependencies).

Here is an implementation:

function topologicalSort(tasks) {
    const visited = new Set;
    const taskMap = new Map(tasks.map(task => [task.id, task]));
    
    function dfs(tasks) {
        for (let task of tasks) {
            if (!visited.has(task.id)) {
                dfs(task.prerequisites_ids.map(id => taskMap.get(id)));
            }
            visited.add(task);
        }
    }
    
    dfs(tasks);
    return [...visited];
}

// Demo on your example:
let tasks = [{"id": "b94ae1a5-c6b2-4e45-87cd-a4036fdb7870","prerequisites_ids": ["2a4fdd9c-45d0-49d9-a0eb-ba5a0464f2b1"]},{"id": "ef7d2415-808f-4efc-939e-2692f38a5ee7","prerequisites_ids": ["74e41a2c-e74e-4016-bb2c-f2e84c04fe92"]},{"id": "74e41a2c-e74e-4016-bb2c-f2e84c04fe92","prerequisites_ids": []},{"id": "2a4fdd9c-45d0-49d9-a0eb-ba5a0464f2b1","prerequisites_ids": ["ef7d2415-808f-4efc-939e-2692f38a5ee7"]}];
console.log(topologicalSort(tasks));

How can I sort a javascript array of objects that specify prerequisites between them?

1 Answers1