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.
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.
- Great question, but I'm not sure it belongs here. Perhaps on CodeReview? – RobG Commented Feb 11, 2016 at 2:29
- Thanks RobG. I didn't know there is a CodeReview munity, will move it over. – Lee Commented Feb 11, 2016 at 2:37
- The array.sort() cannot take f(n) amount of time, any sort algorithm cannot perform better than O(n log n) in the average or worst case, en.wikipedia/wiki/Sorting_algorithm – Alex Vazhev Commented Feb 11, 2016 at 3:17
2 Answers
Reset to default 10You can use a recursive algorithm and hash object, I believe that performance of this algorithm will take about O(n log n):
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]);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 sorting order, please change heirarchySortFunc():
function hierarchySortFunc(a,b ) {
return a.name < b.name;
}
It might be simpler just to bine 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.binedName = getCombinedName(item);
})
var sortedArray = array.sort(function(a,b) {
return a.binedName > b.binedName;
});Result:
{_id: 4, parent: 0, name: "A", binedName: "A"}
{_id: 5, parent: 4, name: "M", binedName: "AM"}
{_id: 6, parent: 4, name: "N", binedName: "AN"}
{_id: 1, parent: 0, name: "Z", binedName: "Z"}
{_id: 2, parent: 1, name: "H", binedName: "ZH"}
{_id: 8, parent: 2, name: "G", binedName: "ZHG"}
{_id: 7, parent: 2, name: "L", binedName: "ZHL"}
{_id: 3, parent: 1, name: "Z", binedName: "ZZ"}