Ordina array di oggetti con la gerarchia di gerarchia e nome

Question

ho un array di oggetti nidificati:

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

ho bisogno di ordinarli nel modo per i nodi allo stesso livello verranno ordinati in ordine alfabetico (crescente/desc configurable) e tutti i nodi figli dovrebbero essere dopo il loro genitore e prima del nodo fratello genitore anche ordinati per ordine alfabetico.

Ad esempio, se filtrate per asc, l'uscita dovrebbe essere

[ 
    { _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 uscita, 4 è prima 1 perché A < Z. 5 e 6 sono in ordine alfabetico sotto 4 e prima 1. Caso simile per 8 e 7 ai punti 2 e 3. prima

e se desc, l'uscita dovrebbe essere:

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

ho cercato di implementare una funzione come sotto.

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

Supponendo Array.sort() prendere f(n) quantità di tempo durante l'ordinamento per asc genitore per una serie di lunghezza n, sto facendo un po 'di analisi delle prestazioni per l'attuazione, come di seguito.

Il caso: f (n) + x * n + y * sum (1 a n/2) * n

caso peggiore: f (n) + x * n + y * sum (Da 1 a n) * n;

x - fattore nell'elaborazione di un dato elemento in arr.

y - fattore nell'elaborare qualsiasi dato elemento in arr contro qualsiasi elemento in arr2.

Come si può vedere, in entrambi i casi, la durata di esecuzione crescerà in modo esponenziale come n cresce, quindi mi chiedo se posso fare qualcosa per migliorare questo.

Answer 1

È possibile utilizzare un algoritmo ricorsivo e oggetto hash, credo che le prestazioni di questo algoritmo vorrà circa 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> 

Risultato:

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

Se si desidera per cambiare l'ordinamento, per favore cambia heirarchySortFunc():

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