sorting an array of objects JS - Javascript

Tiltmode
April 15, 2023
162 views
3 votes
4 Answers

Hello everyone I still can’t sort the array correctly. We need to sort the following array:

const arr = [
     {id: 3123124, parentId: 0o0000, title: 'title', type: 'block'},
     {id: 3542132, parentId: 3123124, title: 'title', type: 'child'},
     {id: 12345, parentId: 88888, title: 'title', type: 'block'},
     {id: 24124, parentId: 12345, title: 'title', type: 'child'},
     {id: 99999, parentId: 45324, title: 'title', type: 'child'},
     {id: 986648, parentId: 3123124, title: 'title', type: 'block'},
     {id: 77777, parentId: 88888, title: 'title', type: 'child'},
     {id: 54232, parentId: 3123124, title: 'title', type: 'child'},
     {id: 54308, parentId: 15075, title: 'title', type: 'child'},
     {id: 66666, parentId: 88888, title: 'title', type: 'block'},
     {id: 56445, parentId: 12345, title: 'title', type: 'child'},
     {id: 88888, parentId: 45324, title: 'title', type: 'block'},
     {id: 15075, parentId: 12345, title: 'title', type: 'block'},
     {id: 84356, parentId: 66666, title: 'title', type: 'child'},
     {id: 45324, parentId: 0o0000, title: 'title', type: 'block'},
]

const newArr = [
    {id: 3123124, parentId: 0o0000, title: 'title', type: 'block'},
    {id: 3542132, parentId: 3123124, title: 'title', type: 'child'},
    {id: 54232, parentId: 3123124, title: 'title', type: 'child'},
    {id: 986648, parentId: 3123124, title: 'title', type: 'block'},
    {id: 45324, parentId: 0o0000, title: 'title', type: 'block'},
    {id: 99999, parentId: 45324, title: 'title', type: 'child'},
    {id: 88888, parentId: 45324, title: 'title', type: 'block'},
    {id: 77777, parentId: 88888, title: 'title', type: 'child'},
    {id: 12345, parentId: 88888, title: 'title', type: 'block'},
    {id: 56445, parentId: 12345, title: 'title', type: 'child'},
    {id: 24124, parentId: 12345, title: 'title', type: 'child'},
    {id: 15075, parentId: 12345, title: 'title', type: 'block'},
    {id: 54308, parentId: 15075, title: 'title', type: 'child'},
    {id: 66666, parentId: 88888, title: 'title', type: 'block'},
    {id: 84356, parentId: 66666, title: 'title', type: 'child'},
]

arr – array to sort
newArr – is an array that should turn out to be

So that the topmost elements have parentId: 0o000, and their lowest children, who have the same parentId id, and so on, there can be as many elements as you like.
If the parentId is the same for several elements, then child comes first, the most recent block and its children below, if there are any.

I tried to add to a new array by the parentId property, but in the end the order of the elements was lost

Answers

You will need to build a tree structure which maps a parent to its children (I am using a Map here to do that, other implementations are also possible). Once you have that tree structure you just need to first print the key, then all the children and do that for every node.
As you do not want to print the root node with id 0 you have to ignore this node before printing it.

const arr = [
     {id: 3123124, parentId: 0o0000, title: 'title', type: 'block'},
     {id: 3542132, parentId: 3123124, title: 'title', type: 'child'},
     {id: 12345, parentId: 88888, title: 'title', type: 'block'},
     {id: 24124, parentId: 12345, title: 'title', type: 'child'},
     {id: 99999, parentId: 45324, title: 'title', type: 'child'},
     {id: 986648, parentId: 3123124, title: 'title', type: 'block'},
     {id: 77777, parentId: 88888, title: 'title', type: 'child'},
     {id: 54232, parentId: 3123124, title: 'title', type: 'child'},
     {id: 54308, parentId: 15075, title: 'title', type: 'child'},
     {id: 66666, parentId: 88888, title: 'title', type: 'block'},
     {id: 56445, parentId: 12345, title: 'title', type: 'child'},
     {id: 88888, parentId: 45324, title: 'title', type: 'block'},
     {id: 15075, parentId: 12345, title: 'title', type: 'block'},
     {id: 84356, parentId: 66666, title: 'title', type: 'child'},
     {id: 45324, parentId: 0o0000, title: 'title', type: 'block'},
];

// build a lookup table for efficient lookups of an object
const lookup = arr.reduce((acc, cur) => (acc.set(cur.id, cur), acc), new Map());

// build tree with parentId as key and an array of child IDs as values
const mapping = arr.reduce((acc, cur) => {
  if(acc.has(cur.parentId)) acc.set(cur.parentId, [...acc.get(cur.parentId), cur.id])
  else acc.set(cur.parentId, [cur.id])
  return acc;
}, new Map());

// we do not care about the root node
mapping.delete(0);

// map keys and their values in a flat structure
// use lookup table to replace IDs with actual objects
const result = [...mapping.entries()].flatMap(([key, values]) => ([lookup.get(key), ...values.map(v => lookup.get(v))]));
console.log(JSON.stringify(result))

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

The order in which the groups are printed differs slightly from what you have shown, the groups however are correct. If you want to have a particular order you just have to sort [...mapping.entries()] accordingly before using flatMap() to print the values.

You could take an object as lookup for the id and another object for grouping by parents and then get all items in order of parents first, sorted by block first at each level.

const
    getItems = parent => (parents[parent] || [])
        .sort((a, b) => (ids[a].type === 'block') - (ids[b].type === 'block'))
        .flatMap(id => [ids[id], ...getItems(id)]),
    data = [{ id: 3123124, parentId: 0o0000, title: 'title', type: 'block' }, { id: 3542132, parentId: 3123124, title: 'title', type: 'child' }, { id: 12345, parentId: 88888, title: 'title', type: 'block' }, { id: 24124, parentId: 12345, title: 'title', type: 'child' }, { id: 99999, parentId: 45324, title: 'title', type: 'child' }, { id: 986648, parentId: 3123124, title: 'title', type: 'block' }, { id: 77777, parentId: 88888, title: 'title', type: 'child' }, { id: 54232, parentId: 3123124, title: 'title', type: 'child' }, { id: 54308, parentId: 15075, title: 'title', type: 'child' }, { id: 66666, parentId: 88888, title: 'title', type: 'block' }, { id: 56445, parentId: 12345, title: 'title', type: 'child' }, { id: 88888, parentId: 45324, title: 'title', type: 'block' }, { id: 15075, parentId: 12345, title: 'title', type: 'block' }, { id: 84356, parentId: 66666, title: 'title', type: 'child' }, { id: 45324, parentId: 0o0000, title: 'title', type: 'block' }],
    parents = data.reduce((r, { id, parentId }) => ((r[parentId] ??= []).push(id), r), {}),
    ids = Object.fromEntries(data.map(o => [o.id, o])),
    sorted = getItems(0);

console.log(sorted);

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

My approach is to use a function to get children for each parent(and their children) recursively:

function getChildren(arr, parentId) {
  const children = arr.filter((item) => item.parentId === parentId);
  // Filter by child type, children with type "child" first, then children with type "block"
  const childrenTypeChild = children.filter((child) => child.type === "child");
  const childrenTypeBlock = children.filter((child) => child.type === "block");
  const sortedChildrenByType = [...childrenTypeChild, ...childrenTypeBlock];

  // Recursively getting children of each child
  return sortedChildrenByType.reduce((acc, child) => {
    acc.push(child, ...getChildren(arr, child.id));
    return acc;
  }, []);
}

const arr = [
  { id: 3123124, parentId: 0o0000, title: "title", type: "block" },
  { id: 3542132, parentId: 3123124, title: "title", type: "child" },
  { id: 12345, parentId: 88888, title: "title", type: "block" },
  { id: 24124, parentId: 12345, title: "title", type: "child" },
  { id: 99999, parentId: 45324, title: "title", type: "child" },
  { id: 986648, parentId: 3123124, title: "title", type: "block" },
  { id: 77777, parentId: 88888, title: "title", type: "child" },
  { id: 54232, parentId: 3123124, title: "title", type: "child" },
  { id: 54308, parentId: 15075, title: "title", type: "child" },
  { id: 66666, parentId: 88888, title: "title", type: "block" },
  { id: 56445, parentId: 12345, title: "title", type: "child" },
  { id: 88888, parentId: 45324, title: "title", type: "block" },
  { id: 15075, parentId: 12345, title: "title", type: "block" },
  { id: 84356, parentId: 66666, title: "title", type: "child" },
  { id: 45324, parentId: 0o0000, title: "title", type: "block" }
];

const parentIds = [...new Set(arr.map((item) => item.parentId))];
const parents = arr
  .filter((item) => parentIds.includes(item.id))
  .sort((parentA, parentB) => parentA.parentId - parentB.parentId);

const newArr = parents.reduce((acc, parent) => {
  // Chech whether array is already sorted
  if (acc.length >= arr.length) {
    return acc;
  }

  // Recursively getting children of each parent
  acc.push(parent, ...getChildren(arr, parent.id));
  return acc;
}, []);

You can define a recursive sortItems function.
It searches for items in the array with the item identifier (parentId or id respectively ) equals the identifier from the function argument. If the parent exists, it is added to sortedArr. Next,
the children items are sorted. For clarity sortItems uses two helper functions: getParent and getChildren.

const arr = [
    { id: 3123124, parentId: 0o0000, title: 'title', type: 'block' },
    { id: 3542132, parentId: 3123124, title: 'title', type: 'child' },
    { id: 12345, parentId: 88888, title: 'title', type: 'block' },
    { id: 24124, parentId: 12345, title: 'title', type: 'child' },
    { id: 99999, parentId: 45324, title: 'title', type: 'child' },
    { id: 986648, parentId: 3123124, title: 'title', type: 'block' },
    { id: 77777, parentId: 88888, title: 'title', type: 'child' },
    { id: 54232, parentId: 3123124, title: 'title', type: 'child' },
    { id: 54308, parentId: 15075, title: 'title', type: 'child' },
    { id: 66666, parentId: 88888, title: 'title', type: 'block' },
    { id: 56445, parentId: 12345, title: 'title', type: 'child' },
    { id: 88888, parentId: 45324, title: 'title', type: 'block' },
    { id: 15075, parentId: 12345, title: 'title', type: 'block' },
    { id: 84356, parentId: 66666, title: 'title', type: 'child' },
    { id: 45324, parentId: 0o0000, title: 'title', type: 'block' },
];

const sortedArr = [];

const getParent = (parentId) => arr.find((item) => item.id === parentId);
const getChildren = (parentId) => arr.filter((item) => item.parentId === parentId);

const sortItems = (parentId = 0) => {
    const parent = getParent(parentId);
    if (parent) sortedArr.push(parent);
    const children = getChildren(parentId);
    children.sort((a, b) => (a.type === 'child' ? 0 : 1) - (b.type === 'child' ? 0 : 1));
    children.forEach((child) => sortItems(child.id));

};

sortItems();


console.log(sortedArr);

Please signup or login to give your own answer.

Click here to cancel reply.

sorting an array of objects JS – Javascript

Answers