Sortuj tablicę obiektów z hierarchii hierarchia i nazwy

Question

Mam tablicę zagnieżdżonych obiektów:

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

muszę uporządkować je w sposób dla węzłów na tym samym poziomie będą sortowane według kolejności alfabetycznej (ASC/desc configurable) i wszystkie węzły potomne powinny być po rodzicu i przed węzłem rodzica rodzica również posortowane alfabetycznie.

Na przykład, w przypadku porządku ASC, dane wyjściowe powinny być

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

W wyjściu 4 jest przed 1, ponieważ < Z. 5 i 6 są w porządku alfabetycznym w ustępie 4 i przed 1. podobny przypadek 7 do 8, a na podstawie 2, a przed 3.

jeśli desc, dane wyjściowe powinny być:

[ 
    { _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 próbowali realizować funkcje jak poniżej.

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

Zakładając Array.sort() podejmuje f(n) czas podczas sortowania według dominującej ASC dla tablicy długości n, robię jakieś analizy wydajności dla realizacji jak poniżej.

najlepszym przypadku f (n) + x * n + y * suma (1 n/2) * n

Najgorszy przypadek f (n) + x * n + y * suma (Od 1 do n) * n;

x - współczynnik przetwarzania dowolnego elementu w arr.

y - współczynnik przetwarzania dowolnego elementu w arr względem dowolnego elementu w arr2.

Jak widać, w obu przypadkach, czas realizacji wzrośnie wykładniczo n rośnie, więc zastanawiam się, czy mogę coś zrobić, aby poprawić ten wynik.

Answer 1

Można użyć rekurencyjny algorytm i obiekt hash, wierzę, że wydajność tego algorytmu zajmie około 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> 

Wynik:

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

Jeśli chcesz aby zmienić kolejność sortowania, należy zmienić heirarchySortFunc():

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