Creating a Javascript sort algorithm which orders mentioned items immediately after itself

Question

I'm trying to create a sort algo, that takes a list of items. Each item has the chance to define which item it comes after, if it doesn't then its natural position will be preserved based off the initial sorting.

Given the data set looks like.....

[
    {
        "id": 1871,
        "after": null,
    },
    {
        "id": 1872,
        "after": null,
    },
    {
        "id": 1873,
        "after": 1872,
    },
    {
        "id": 1874,
        "after": 1872,
    },
    {
        "id": 1875,
        "after": 1873,
    },
    {
        "id": 1876,
        "after": 1875,
    },
    {
        "id": 1877,
        "after": 1876,
    },
    {
        "id": 1878,
        "after": 1877,
    },
    {
        "id": 1879,
        "after": null,
    },
    {
        "id": 1880,
        "after": 1874,
    },
]

The idea is that it recursively sorts the array until it's resolved as possible, placing the items in the correct order based numerically from the "id" property, if the item contains an "after" value it should be placed immediately after the element, So the correct order would look like.....

[
    {
        "id": 1871,
        "after": null,
    },
    {
        "id": 1872,
        "after": null,
    },
    {
        "id": 1873,
        "after": 1872,
    },
        {
        "id": 1875,
        "after": 1873,
    },
    {
        "id": 1876,
        "after": 1875,
    },
    {
        "id": 1877,
        "after": 1876,
    },
    {
        "id": 1878,
        "after": 1877,
    },
    {
        "id": 1874,
        "after": 1872,
    },
    {
        "id": 1880,
        "after": 1874,
    },
    {
        "id": 1879,
        "after": null,
    },
]

Can somebody provide a sort function that can solve this?

Thanks

Looks like you're better off grouping by `id`->`after` and then flattening. — pilchard, May 03 '23 at 16:42
When comparing the elements, first compare the "after" of each with the "id" of the other. If there's no "after" relationship, or if the "after" references are irrelevant, then all that matters is the "id". — Pointy, May 03 '23 at 16:44
And I think you can do this with the built-in `.sort()` method. — Pointy, May 03 '23 at 16:45
Actually I am not sure your problem statement makes sense. Which is more important: the "id" ordering or the "after" ordering? Your description makes it seem like the "after" ordering is more important, but your desired result does not conform to that. — Pointy, May 03 '23 at 16:52
For example, why would 1879 come *after* 1880? The two have nothing to do with each other, so 1879 and 1880 should be compared purely by id. 1879 should come before 1880, and the resulting ordering still has 1880 coming after 1874. — Pointy, May 03 '23 at 16:53
The `id` in the example is auto-inc values, so they'll be in the correct order to start with, however I need to then move all the items which reference another item in the array immediately after it, effectively we're going from a nested structure to a flattened one — owenmelbz, May 03 '23 at 16:54
Still does not make sense. Specifically: why does 1879 come after 1880 in the result? — Pointy, May 03 '23 at 16:54
1879 comes after 1880 because 1880 is only there because its been placed after 1874, and 1879 comes after 1874 — owenmelbz, May 03 '23 at 16:57
Then it's tree building which can then be flattened. see [Build tree array from flat array in javascript](https://stackoverflow.com/questions/18017869/build-tree-array-from-flat-array-in-javascript) — pilchard, May 03 '23 at 16:59

pilchard · Answer 1 · 2023-05-19T11:48:39.107

The order you're looking for is a preorder flattening of the data after it's been converted to a tree. Here's a quick implementation.

const input = [{ id: 1871, after: null, }, { id: 1872, after: null, }, { id: 1873, after: 1872, }, { id: 1874, after: 1872, }, { id: 1875, after: 1873, }, { id: 1876, after: 1875, }, { id: 1877, after: 1876, }, { id: 1878, after: 1877, }, { id: 1879, after: null, }, { id: 1880, after: 1874, },];

// build the tree
const tree = input.reduce((a, node) => {
  (a[node.after] ??= []).push({ node, afters: (a[node.id] ??= []) });

  return a;
}, {})['null'];

// recursive depth-first traversal
function flatten(arr) {
  let result = [];

  for (const { node, afters } of arr) {
    result.push(node, ...flatten(afters));
  }

  return result;
}

console.log(flatten(tree));

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

You could shorten the flatten() function to a single line, but it may be a little less efficient due to the number of intermediate arrays it creates and the need to flat() them afterwards

const flatten = (arr) =>
  arr.flatMap(({ node, afters }) => [node, ...flatten(afters)]);

Here are generalized depth-first and breadth-first methods based on the above.

function toTree(arr, parentProp = 'parent', rootProp = 'null') {
  return arr.reduce((a, node) => {
    (a[node[parentProp]] ??= []).push({ node, children: (a[node.id] ??= []) });
    
    return a;
  }, {})[rootProp];
}

function sortDepthFirst(arr, parentProp, rootProp) {
  const flatten = (arr) => {
    let result = [];
    for (const { node, children } of arr) {
      result.push(node, ...flatten(children));
    }
    return result;
  };

  return flatten(toTree(arr, parentProp, rootProp));
}

function sortBreadthFirst(arr, parentProp, rootProp) {
  const result = [];
  
  let queue = toTree(arr, parentProp, rootProp);
  while (queue.length) {
    const { node, children } = queue.shift();
    result.push(node);
    queue.push(...children);
  }

  return result;
}

const input = [{ id: 1871, after: null, }, { id: 1872, after: null, }, { id: 1873, after: 1872, }, { id: 1874, after: 1872, }, { id: 1875, after: 1873, }, { id: 1876, after: 1875, }, { id: 1877, after: 1876, }, { id: 1878, after: 1877, }, { id: 1879, after: null, }, { id: 1880, after: 1874, },];

console.log(sortDepthFirst(input, 'after', null));
console.log(sortBreadthFirst(input, 'after', null));

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

Ah this seems to do the job thanks! Will mark as accepted after a little more testing :) thanks — owenmelbz, May 04 '23 at 08:21
No worries, glad it helped. Definitely test further it was a quick write up. You can also search further for depth-first traversal and tree-building. — pilchard, May 04 '23 at 08:45

Creating a Javascript sort algorithm which orders mentioned items immediately after itself

1 Answers1