Sorting an array of objects with a hierarchy by hierarchy and name

Question

I have an array of nested objects:

[ {_id:1, parent:0, name:'Z'}, {_id:4, parent:0, name:'A'}, {_id:2, parent:1, name:'H'}, {_id:8, parent:2, name:'G'}, {_id:5, parent:4, name:'M'}, {_id:6, parent:4, name:'N'}, {_id:3, parent:1, name:'Z'}, {_id:7, parent:2, name:'L'} ] 

I need to sort them so that nodes at the same level are sorted alphabetically (asc / desc configurable), and all child nodes should be after their parent and before their sibling node is also sorted alphabetically.

For example, if sorted by asc, the output should be

 [ { _id: 4, parent: 0, name: 'A' }, { _id: 5, parent: 4, name: 'M' }, { _id: 6, parent: 4, name: 'N' }, { _id: 1, parent: 0, name: 'Z' }, { _id: 2, parent: 1, name: 'H' }, { _id: 8, parent: 2, name: 'G' }, { _id: 7, parent: 2, name: 'L' }, { _id: 3, parent: 1, name: 'Z' } ] 

Output 4 is before 1, since A <Z. 5 and 6 are sorted alphabetically under 4 and up to 1. A similar case for 8 and 7 under 2 and up to 3.

and if desc, the output should be:

 [ { _id: 1, parent: 0, name: 'Z' }, { _id: 3, parent: 1, name: 'Z' }, { _id: 2, parent: 1, name: 'H' }, { _id: 7, parent: 2, name: 'L' }, { _id: 8, parent: 2, name: 'G' }, { _id: 4, parent: 0, name: 'A' }, { _id: 5, parent: 4, name: 'M' }, { _id: 6, parent: 4, name: 'N' } ] 

I tried to implement a function as shown below.

 function sortByHierarchyAndName(arr, sort) { var i = 0; j = 0; t = 0; parentFound = false; x = arr.length; arr2 = []; //Sort by parent asc first arr = arr.sort(function(a, b) { if(a.parent < b.parent) return -1; if(a.parent > b.parent) return 1; return 0; }); for(; i < x; i += 1) { t = arr2.length; if(t === 0) arr2.push(arr[i]); else if(arr[i].parent === 0) { for(j = 0; j < t; j += 1) { if(sort === -1) { if(arr[i].name >= arr2[j].name) arr2.splice(j, 0, arr[i]); } else { if(arr[i].name <= arr2[j].name) arr2.splice(j, 0, arr[i]); } } if(arr2.length === t) arr2.push(arr[i]); } else { parentFound = false; for(j = 0; j < t; j += 1) { if(arr[i].parent === arr2[j]._id) { if(j === t - 1) { arr2.push(arr[i]); } parentFound = true; } else if(arr[i].parent === arr2[j].parent) { if(sort === -1) { if(j === t - 1) arr2.push(arr[i]); else if(arr[i].name >= arr2[j].name) { arr2.splice(j, 0, arr[i]); j = t; } } else { if(j === t - 1) arr2.push(arr[i]); else if(arr[i].name <= arr2[j].name) { arr2.splice(j, 0, arr[i]); j = t; } } } else if(arr[i].parent > arr2[j].parent && parentFound) { arr2.splice(j, 0, arr[i]); j = t; } } } } return arr2; } 

Assuming array.sort () takes f(n) amount of time sorted by parent asc for an array of length n , I do some performance analysis for the implementation, as shown below.

Best case: f (n) + x * n + y * sum (1 to n / 2) * n

Worst case: f (n) + x * n + y * sum (1 to n) * n;

x is the coefficient when processing any given element in arr.

y is the coefficient when processing any given element in arr against any element in arr2.

As you can see, in both cases, the execution time will increase exponentially as n grows, so I wonder if I can do something to improve this.

Answer 1

You can use a recursive algorithm and a hash object, I believe that the performance of this algorithm will take about O (n log n):

 <script> function hierarchySortFunc(a,b ) { return a.name > b.name; } function hierarhySort(hashArr, key, result) { if (hashArr[key] == undefined) return; var arr = hashArr[key].sort(hierarchySortFunc); for (var i=0; i<arr.length; i++) { result.push(arr[i]); hierarhySort(hashArr, arr[i]._id, result); } return result; } var arr = [ { _id: 4, parent: 0, name: 'A' }, { _id: 5, parent: 4, name: 'M' }, { _id: 6, parent: 4, name: 'N' }, { _id: 1, parent: 0, name: 'Z' }, { _id: 2, parent: 1, name: 'H' }, { _id: 8, parent: 2, name: 'G' }, { _id: 7, parent: 2, name: 'L' }, { _id: 3, parent: 1, name: 'Z' } ] var hashArr = {}; for (var i=0; i<arr.length; i++) { if (hashArr[arr[i].parent] == undefined) hashArr[arr[i].parent] = []; hashArr[arr[i].parent].push(arr[i]); } var result = hierarhySort(hashArr, 0, []); for (var i=0; i<result.length; i++) console.log(result[i]); </script> 

Result:

 {_id: 4, parent: 0, name: "A"} {_id: 5, parent: 4, name: "M"} {_id: 6, parent: 4, name: "N"} {_id: 1, parent: 0, name: "Z"} {_id: 2, parent: 1, name: "H"} {_id: 8, parent: 2, name: "G"} {_id: 7, parent: 2, name: "L"} {_id: 3, parent: 1, name: "Z"} 

If you want to change the sort order, please change heirarchySortFunc ():

 function hierarchySortFunc(a,b ) { return a.name < b.name; } 

Answer 2

It may be easier to simply combine the names of the elements and sort them alphabetically.

 var array = [ {_id:1, parent:0, name:'Z'}, {_id:4, parent:0, name:'A'}, {_id:2, parent:1, name:'H'}, {_id:8, parent:2, name:'G'}, {_id:5, parent:4, name:'M'}, {_id:6, parent:4, name:'N'}, {_id:3, parent:1, name:'Z'}, {_id:7, parent:2, name:'L'} ] var getItemFromID = function(id) { return array.filter(function(item){ return item._id === id; })[0] } var getCombinedName = function(item) { var parent = getItemFromID(item.parent); if (parent) { return getCombinedName(parent) + item.name; } else { return item.name; } } array.forEach(function(item){ item.combinedName = getCombinedName(item); }) var sortedArray = array.sort(function(a,b) { return a.combinedName > b.combinedName; }); 

Result:

 {_id: 4, parent: 0, name: "A", combinedName: "A"} {_id: 5, parent: 4, name: "M", combinedName: "AM"} {_id: 6, parent: 4, name: "N", combinedName: "AN"} {_id: 1, parent: 0, name: "Z", combinedName: "Z"} {_id: 2, parent: 1, name: "H", combinedName: "ZH"} {_id: 8, parent: 2, name: "G", combinedName: "ZHG"} {_id: 7, parent: 2, name: "L", combinedName: "ZHL"} {_id: 3, parent: 1, name: "Z", combinedName: "ZZ"}