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 in the way for nodes at same level will be sorted by alphabetic order (asc/desc configurable) and all child nodes should be after their parent and before their parent's sibling node also sorted by alphabetic order.
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' }
]
In the output, 4 is before 1 because A < Z. 5 and 6 are sorted alphabetically under 4 and before 1. Similar case for 8 and 7 under 2 and before 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 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() take f(n)
amount of time when sorting by parent asc for an array of length n
, I'm doing some performance analysis for the implementation as 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 - factor in processing any given element in arr.
y - factor in processing any given element in arr against any element in arr2.
As you can see, in both case, the duration of execution will grow exponentially as n
grows, so I'm wondering if I can do something to improve this.
Hierarchical sorting, or multiple-key sorting, allows you to sort data according to multiple sorting criteria in a hierarchical manner. This means that the first criterion is the basis for sorting. Any ties are resolved using the second criterion, any remaining ties are resolved using the third criterion, and so on.
You can use the sort function: var sorted = data. sort(function(a, b){ if( a. bayid === b.
To sort an array of objects, use the sort() method with a compare function. A compareFunction applies rules to sort arrays by defined our own logic. They allow us to sort arrays of objects by strings, integers, dates, or any other custom property.
We can sort the array of objects using the sort() method in javascript and then provide a comparison function that will ultimately determine the order of the objects. A compare Function applies rules to sort arrays that are defined by our logic.
It might be simpler just to combine the item names and sort 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"}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With