Sort Array von Objekten mit der Hierarchie von Hierarchie und den Namen

Question

I ein Array von verschachtelten Objekten haben:

[ 
    {_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'} 
] 

Ich brauche sie in der Art und Weise für die Knoten auf dem gleichen Niveau zu sortieren, wird alphabetisch sortiert werden (auf/desc konfigurierbar) und alle Kindknoten sollten nach ihrem Elternknoten und vor dem Geschwisterknoten ihres Elternteils ebenfalls nach alphabetischer Reihenfolge sortiert sein.

Zum Beispiel durch ASC sortiert, wenn, sollte die Ausgabe

[ 
    { _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' } 
] 

Im ausgegeben werden, 4 ist, bevor 1, da A < Z. 5 und 6 in alphabetischer Reihenfolge unter 4 und vor dem 1. ähnlichen Fall sortiert für 8 bzw. 7 unter 2 und vor dem 3.

und wenn DESC, sollte der Ausgang sein:

[ 
    { _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 eine Funktion, wie unten umzusetzen versucht.

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; 
} 

Angenommen Array.sort() nehmen f(n) Menge an Zeit, wenn sie von Mutter ASC für ein Array mit einer Länge von Sortier n, ich dabei einige Leistungsanalyse für die Umsetzung, wie unten.

Bester Fall: f (n) + x * n + y * sum (1 bis n/2) * n

Worst case: f (n) + x * n + Summe y * (1 bis n) * n;

x - Faktor bei der Verarbeitung eines beliebigen Elements in arr.

y - Faktor bei der Verarbeitung eines beliebigen Elements in arr gegen ein Element in arr2.

Wie Sie sehen können, in beiden Fällen wird die Dauer der Ausführung exponentiell wachsen, wie n wächst, so frage ich mich, ob ich etwas tun kann, dies zu verbessern.

Answer 1

Sie einen rekursiven Algorithmus und Hash-Objekt verwenden kann, glaube ich, dass die Leistung dieses Algorithmus zu O (n log n) statt:

<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> 

Ergebnis:

{_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"} 

Wenn Sie möchten, Um die Sortierreihenfolge zu ändern, ändern Sie bitte hirarchieSortFunc():

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