I have a 2D array whose entries represent an employee including the name of their manager, sort of like this:

var array = [["Name", "Manager"],
["Leonard", "Penny"],
["Penny", "Professor Proton"],
["Sheldon", "Bernadette"],
["Raj", "Penny"],
["Professor Proton", "Professor Proton"],
["Howard", "Bernadette"],
["Bernadette", "Professor Proton"]]

If the employee and the manager are the same, it means that the person is highest up in the hierarchy. What I want to achieve is to sort each employee below their manager, alphabetically. In other words, the output I want is this:

[["Name", "Manager"],
["Professor Proton", "Professor Proton"],
["Bernadette", "Professor Proton"],
["Howard", "Bernadette"],
["Sheldon", "Bernadette"],
["Penny", "Professor Proton"],
["Leonard", "Penny"],    
["Raj", "Penny"]]

My attempt was to use array.sort(compare) with the following "compare" function:

var array = [
  ["Name", "Manager"],
  ["Leonard", "Penny"],
  ["Penny", "Professor Proton"],
  ["Sheldon", "Bernadette"],
  ["Raj", "Penny"],
  ["Professor Proton", "Professor Proton"],
  ["Howard", "Bernadette"],
  ["Bernadette", "Professor Proton"]
];

function compare(a, b) {

  if (a[0] === a[1]) {
    return -1;
  }

  if (b[0] === b[1]) {
    return 1;
  }

  if (a[0] === b[1]) {
    return -1;
  }

  if (b[0] === a[1]) {
    return 1;
  }


  if (a[0].toLowerCase() < b[0].toLowerCase()) {
    return -1;
  }

  if (a[0].toLowerCase() > b[0].toLowerCase()) {
    return 1;
  }

  return 0;
}

console.log(array.sort(compare));

Unfortunately, what I get as output is just an array sorted alphabetically by the name of the employee. Plus, the "header" is included in the sort as well, which I want not to happen.

What am I doing wrong, any tips or alternative suggestions other than using Array.prototype.sort()?

Please, kind soul, help me!

CodePudding user response：

You need a topological sorting and get the itmes as flat array from a tree.

const
    sort = array => {
        const
            getNames = manager => employee => [
                [employee, manager || employee],
                ...(t[employee] || [])
                    .sort(([a], [b]) => a.localeCompare(b))
                    .flatMap(getNames(employee))
            ],
            root = [],
            t = {};

        array.forEach(([employee, manager]) => {            
            if (employee === manager) manager = '';
            (t[manager] ??= []).push(employee);
        });

        return t[''].flatMap(getNames(''));
    },
    data = [["Name", "Manager"], ["Leonard", "Penny"], ["Penny", "Professor Proton"], ["Sheldon", "Bernadette"], ["Raj", "Penny"], ["Professor Proton", "Professor Proton"], ["Howard", "Bernadette"], ["Bernadette", "Professor Proton"]],
    result = [data[0], ...sort(data.slice(1))];
    
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

CodePudding user response：

I don't fully understand your goal because your expected results and your explaination don't line up (but it's probably just me not seeing it). But here's something I wrote that I feel is meeting your criteria?

const input = [
  ['Name', 'Manager'],
  ['Leonard', 'Penny'],
  ['Penny', 'Professor Proton'],
  ['Sheldon', 'Bernadette'],
  ['Raj', 'Penny'],
  ['Professor Proton', 'Professor Proton'],
  ['Howard', 'Bernadette'],
  ['Bernadette', 'Professor Proton'],
];

const sort = (arr) => {
  return arr.map(el => [el[1], el[0]]) //swap employee and manager
            .sort() //sort by the first element (i.e. manager)
            .map(el => [el[1], el[0]]) //swap back employee and manager
            .sort((a,b) => b[0] === b[1] ? 1 : -1 ); //move element to front if employee is the manager
}

console.log(sort(input));

It's result is as follows which is different to your expected results but meet the criteria:

[["Professor Proton", "Professor Proton"],
["Penny", "Professor Proton"],
["Bernadette", "Professor Proton"],
["Raj", "Penny"],
["Leonard", "Penny"],
["Name", "Manager"],
["Sheldon", "Bernadette"],
["Howard", "Bernadette"]]

CodePudding user response：

The sort you have described is basically a flattened tree structure.

Here building the tree by reference in a Map, pushing top-level elements (employee === manager) to the tree, then flattening using a queue.

I expanded the dataset to include more properties as an example based on your comment on Nina's answer.

const input = [
  ['Name', 'Manager', 'Shift', 'Language'],
  ['Leonard', 'Penny', 'Day', 'en'],
  ['Penny', 'Professor Proton', 'Day', 'en'],
  ['Sheldon', 'Bernadette', 'Night', 'en'],
  ['Raj', 'Penny', 'Night', 'en'],
  ['Professor Proton', 'Professor Proton', 'Swing', 'en'],
  ['Howard', 'Bernadette', 'Night', 'en'],
  ['Bernadette', 'Professor Proton', 'Day', 'en'],
];

const [head, ...temp] = input;

const map = new Map(temp
  .sort((a, b) => a[0].localeCompare(b[0]))
  .map(([, m]) => [m, []]));
  
const tree = [];
for (const [n, m, ...rest] of temp) {
  const o = { employee: [n, m, ...rest], children: map.get(n) };
  if (n === m) {
    tree.push(o);
  } else {
    map.get(m).push(o);
  }
}

const res = [head];
while (tree.length) {
  const { employee, children } = tree.shift();
  res.push(employee);
  tree.unshift(...(children ?? []));
}

console.log(res);

.as-console-wrapper { max-height: 100% !important; top: 0; }