how to sort recursively in JS

Question

I'm trying to sort an Array type data recursively.

Here's the data structure.

const DATA = [
  {
    id: 123,
    name: "kevin",
    children: [
      {
        id: 345,
        name: "luke",
        children: [
          {
            id: 67895,
            name: "jane",
            children: [{ id: 556, name: "che", children: [] }]
          },
          {
            id: 89760,
            name: "kendrick",
            children: [
              { id: 4627, name: "auro", children: [] },
              { id: 777, name: "civil", children: [] },
              { id: 37654, name: "hobbit", children: [] }
            ]
          }
        ]
      },
      { id: 123215, name: "ron", children: [] }
    ]
  },
  { id: 7642, name: "dobby", children: [] },
  { id: 2589, name: "porter", children: [] }
];

I wanna sort by either 'id' or 'name'.

This is what I tried.

const sorting = (array, label, sortedBy) => {
  if (sortedBy === "asc")
    return array.sort((a, b) => (a[label] > b[label] ? 1 : -1));
  return array.sort((a, b) => (b[label] > a[label] ? 1 : -1));
};

const sortingData = (data, label, sort) => {
  let result;

  for (let i = 0; i < data.length; i++) {
    result = sorting(data, label, sort);
    if (data[i].children && data[i].children.length) {
      result[i].children = sortingData(data[i].children, label, sort);
    }
  }

  return result;
};

// Sample data
const DATA = [
  {
    id: 123,
    name: "kevin",
    children: [
      {
        id: 345,
        name: "luke",
        children: [
          {
            id: 67895,
            name: "jane",
            children: [{ id: 556, name: "che", children: [] }]
          },
          {
            id: 89760,
            name: "kendrick",
            children: [
              { id: 4627, name: "auro", children: [] },
              { id: 777, name: "civil", children: [] },
              { id: 37654, name: "hobbit", children: [] }
            ]
          }
        ]
      },
      { id: 123215, name: "ron", children: [] }
    ]
  },
  { id: 7642, name: "dobby", children: [] },
  { id: 2589, name: "porter", children: [] }
];

const data = sortingData(DATA, "id", "asc");

console.log(data);

In my poor logic, it seems working but not properly working. Because item's children or children's children is not sorted. :(

What should I fix? or maybe my approach was totally wrong?

Thank you so much for your help.

below is what I wanted:

const DATA = [
  {
    id: 123,
    name: "kevin",
    children: [
      {
        id: 345,
        name: "luke",
        children: [
          {
            id: 67895,
            name: "jane",
            children: [{ id: 556, name: "che", children: [] }]
          },
          {
            id: 89760,
            name: "kendrick",
            children: [
              { id: 777, name: "civil", children: [] },
              { id: 4627, name: "auro", children: [] },
              { id: 37654, name: "hobbit", children: [] }
            ]
          }
        ]
      },
      { id: 123215, name: "ron", children: [] }
    ]
  },
  { id: 2589, name: "porter", children: [] },
  { id: 7642, name: "dobby", children: [] }
];

user_1243641 · Answer

As far as I can tell, the code supplied works fine. It makes no change from the initial data because that data is already sorted by ascending ids. But if you change to descending or change to the "name" property, then it works as expected.

But here is another approach, which separates out the recursive sorting from the simpler sorting, and offers some parameterization for that recursive bit, namely that the descendant node is called "children":

const sort = (field, dir = 'asc') => (xs) => 
  [...xs] .sort (dir == 'asc'
    ? ({[field]: a}, {[field]: b}) => a < b ? -1 : a > b ?  1 : 0         
    : ({[field]: a}, {[field]: b}) => a < b ?  1 : a > b ? -1 : 0         
  )

const sortRecursive = (childField) => (sort) => (xs) =>
  sort ([...xs]) .map (({[childField]: cf, ...rest}) => ({
    ...rest, 
    [childField]: sortRecursive (childField) (sort) (cf)
  }))


const DATA = [{id: 123, name: "kevin", children: [{id: 345, name: "luke", children: [{id: 67895, name: "jane", children: [{id: 556, name: "che", children: []}]}, {id: 89760, name: "kendrick", children: [{id: 4627, name: "auro", children: []}, {id: 777, name: "civil", children: []}, {id: 37654, name: "hobbit", children: []}]}]}, {id: 123215, name: "ron", children: []}]}, {id: 7642, name: "dobby", children: []}, {id: 2589, name: "porter", children: []}]

// Build a reusable sort function
const mySort = sortRecursive ('children') (sort ('name')) // defaults to ascending

console .log ('By name, ascending:', mySort (DATA))

// Or call directly:
console .log ('By id, descending:', sortRecursive ('children') (sort ('id', 'desc')) (DATA))

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

Here we write a sort function, which takes the field to sort on, and a direction, which defaults to an ascending sort, and returns a function which takes an array and returns a copy of it sorted by that field and direction. Note that this does not mutate the original array; we're not barbarians here.

Then we add a sortRecursive function which takes the name of a field that holds descendent elements and returns a function that takes a sort function (such as might be returned sort) and returns one more function which takes an array of objects with the given recursive structure and sorts the array and all of its (recursive) descendants. Again note that it does this in an immutable manner.

The main point is that this is now a cleaner breakdown. Our sort function is genuinely reusable, and sortRecursive layers on top of that in a flexible manner.

For instance, this does make the assumption that the data in your sort field can be sorted by <. That may not be the case, and then you might have to use localeCompare or some other technique. But note that this will change sort but sortRecursive will not need to change for it.

There's a temptation to write this instead:

const sort = (field, dir = 'asc') => (xs) => 
  [...xs] .sort (({[field]: a}, {[field]: b}) => (dir == 'asc' ? 1 : -1) * (a < b ? -1 : a > b ? 1 : 0))

It works fine, but it means that on every callback to the comparator made by the sort algorithm, we will need to recheck the direction parameter and perform a multiplication. So, while it is more elegant, it is less efficient.

user_4620771 · Answer

Basically you can change the order of a and b sort params depending on the order param you pass to your custom function. Then also based on the type of current param (string or number) you use different types of sort method.

const DATA = [{"id":123,"name":"kevin","children":[{"id":345,"name":"luke","children":[{"id":67895,"name":"jane","children":[{"id":556,"name":"che","children":[]}]},{"id":89760,"name":"kendrick","children":[{"id":4627,"name":"auro","children":[]},{"id":777,"name":"civil","children":[]},{"id":37654,"name":"hobbit","children":[]}]}]},{"id":123215,"name":"ron","children":[]}]},{"id":7642,"name":"dobby","children":[]},{"id":2589,"name":"porter","children":[]}]

function sortData(data, label, order) {
  data.sort((a, b) => {
    const x = order === 'asc' ? a : b;
    const y = order === 'asc' ? b : a;

    if ([x[label], y[label]].some(e => typeof e === 'string')) {
      return x[label].localeCompare(y[label])
    } else {
      return x[label] - y[label]
    }
  })

  data.forEach(el => {
    if (el.children) {
      sortData(el.children, label, order)
    }
  })
}

sortData(DATA, 'name', 'desc')

console.log(JSON.stringify(DATA, 0, 4))

user_18755490 · Answer

let array = [2, 7, 6, 4, 8, 9];

function recursionSort(arr) {
  // If array length is equal to 1 then we need to return the array below at the end of function to (recursive call)
  if (arr.length === 1) {
    return arr;
  }
  // Storing last element inside the temp variable
  let temp = arr.pop();
  // Calling function again
  arr = recursionSort(arr);
  // Passing the array and poped element to "insertElement" function because we need to add that element at particular place where it belongs to
  arr = insertElement(arr, temp);
  // This return is used to complete all iterations(Till this return return the arr to recursive call above "recursionSort(arr)") & at the end we are returining arr to the start position
  return arr;
}

// insertElement function
function insertElement(arr, temp) {
  if (arr.length === 0) {
    // If our array length is 0 then we need to add that element at last & also we have to return the array.
    arr.push(temp);
    return arr;
  } else if (arr[0] >= temp) {
    // if element present at 0th place is bigger than temp, So we have to add that temp at first position & also we have to return the array.
    arr.unshift(temp);
    return arr;
  } else if (arr[arr.length - 1] <= temp) {
    // If element present at last position in array is lesser than temp, So we have to push temp inside array & also we have to return the array.
    arr.push(temp);
    return arr;
  }

  //If above conditions are not satisfying then we are poping the last element inside temp1 and
  let temp1 = arr.pop();
  // again calling inserElement till we are not inserting the temp at the particular place
  arr = insertElement(arr, temp);
  // After inserting temp at there place then we have to push temp1 inside the array
  arr.push(temp1);
  // And at last returning the new array to above function
  return arr;
}

array = recursionSort(array);
console.log("array after SORT:", ...array);

how to sort recursively in JS

3 Answers