I'm doing a sorting algorithm exercise and i'm stuck. I have an array of objects that may contain nested objects like the first, nested on it.

I need to sort all "elements" arrays containing one or more nodes where the "val" property === targetValue are moved to the front of the array.

I need to create a sortObject(object, targetValue) function to do this.

For example:

const object = {
  val: 1,
  elements: [
    {
      val: 2,
      children: [
        {
          val: 7,
          elements: [
            {val: 2},
            {val: 18},
            {val: 12}
          ]
        }
      ]
    },
    {
      val: 4,
      elements: [
        {val: 5},
        {
          val: 6,
          elements: [
            {val: 12},
            {val: 11},
            {val: 10},
            {val: 9},
          ]
        },
        {val: 13}
      ]
    },
    {
      val: 3,
      elements: [
        {val: 15}
      ]
    },
    {
      val: 17,
      elements: [
        {val: 16},
        {
          val: 2,
          elements: [
            {val: 14},
            {val: 11},
            {
              val: 18,
              elements: [
                {val: 4},
                {val: 11},
                {val: 7}
              ]
            },
            {val: 27},
            {val: 18},
            {val: 29},
          ]
        }
      ]
    }
  ]
};

this would become, if i'm calling sortObject(object, 18), (with the changes noted below)

sortedObject = {
  val: 1,
  elements: [
    {
      val: 2,
      elements: [
        {
          val: 7,
          elements: [
            {val: 18}, // <-- this moved up
            {val: 2},
            {val: 12}
          ]
        }
      ]
    },
    {
      val: 17, // <-- this moved up
      elements: [
        {
          val: 2, // <-- this moved up
          elements: [
            {
              val: 18, // <-- this moved up
              elements: [
                {val: 4},
                {val: 11},
                {val: 7}
              ]
            },
            {val: 18}, // <-- this moved up
            {val: 14},
            {val: 11},
            {val: 27},
            {val: 29},
          ]
        },
        {val: 16}
      ]
    },
    {
      val: 4,
      elements: [
        {val: 5},
        {
          val: 6,
          elements: [
            {val: 12},
            {val: 11},
            {val: 10},
            {val: 9},
          ]
        },
        {val: 13}
      ]
    },
    {
      val: 3,
      elements: [
        {val: 15}
      ]
    }
  ]
};

I started creating a sorting algorithm for it, but i couldn't make pass the first "elements" recursion.. and realized that how i was trying to do it would never work (I was creating a new array, getting the indexes of the child objects with the targetValue, and pushing to a new array..but this wouldn't work with the recursion) I'm stuck can anyone help?

CodePudding user response：

You could take a breadth-first search and look for the wanted value and store the object if the value is found. Then sort the array by the boolean value if the set contains the object.

const
    sortObject = (object, value) => {
        const
            hasValue = new Set,
            sort = object => {
                let found = object.val === value;
                if (object.elements) {
                    object.elements.forEach(o => found = sort(o) || found);
                    object.elements.sort((a, b) => hasValue.has(b) - hasValue.has(a));
                }
                if (found) hasValue.add(object);
                return found;
            };

        sort(object);
        return object;
    },
    object = { val: 1, elements: [{ val: 2, elements: [{ val: 7, elements: [{ val: 2 }, { val: 18 }, { val: 12 }] }] }, { val: 4, elements: [{ val: 5 }, { val: 6, elements: [{ val: 12 }, { val: 11 }, { val: 10 }, { val: 9 }] }, { val: 13 }] }, { val: 3, elements: [{ val: 15 }] }, { val: 17, elements: [{ val: 16 }, { val: 2, elements: [{ val: 14 }, { val: 11 }, { val: 18, elements: [{ val: 4 }, { val: 11 }, { val: 7 }] }, { val: 27 }, { val: 18 }, { val: 29 }] }] }] };

console.log(sortObject(object, 18));

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

CodePudding user response：

If the sort order is defined by how deep the occurrence of 18 is, such that the less deep it occurs the earlier it should occur in the array, then I would suggest a kind of bucket sort, where elements that have 18 occurring at the same depth, will be placed in the same bucket. The buckets are then concatenated to become the sorted elements array:

function sortObject(obj, target) {
    const partition = {};
    let minDepth = 10000; // depth of object should not exceed this limit
    if (obj.elements?.length) {
        for (const child of obj.elements) {
            const depth = sortObject(child, target);
            (partition[depth] ??= []).push(child);
            minDepth = Math.min(minDepth, depth);
        }
        obj.elements = Object.values(partition).flat();
    }
    return obj.val === target ? 0 : minDepth   (minDepth < 10000);
}

const object = {val: 1,elements: [{val: 2,elements: [{val: 7,elements: [{val: 2},{val: 18},{val: 12}]}]},{val: 4,elements: [{val: 5},{val: 6,elements: [{val: 12},{val: 11},{val: 10},{val: 9},]},{val: 13}]},{val: 3,elements: [{val: 15}]},{val: 17,elements: [{val: 16},{val: 2,elements: [{val: 14},{val: 11},{val: 18,elements: [{val: 4},{val: 11},{val: 7}]},{val: 27},{val: 18},{val: 29},]}]}]};
sortObject(object, 18);
console.log(object);