Sorting a Javascript array when sort ordering information is available for only some items

user_11981195 0
Viewed 157

I have a data array -

let data = ['x1', 'x2', 'x3', 'x4'];

and another 2d array that specifies the sort order of the elements within the data array -

let order =
    [
        ['x4', 'x1'],
        ['x3', 'x2']
    ];

EDITED: Removed the conflicting rules from the order array

The 'order' array provides ordering data for only some of the elements in the data array. The order of items that are not provided in the 'order' array doesn't matter.

I am using the below logic -

console.log("Before sort:", data);

data.sort((a, b) => {
    console.log("a:", a, ",", "b:", b);

    for (orderRow of order) {
        if (orderRow.includes(a) && orderRow.includes(b)) {
            return orderRow.indexOf(a) - orderRow.indexOf(b);
        }
    }

    return 0;
});

console.log("After sort:", data);

Below is the output -

Before sort: [ 'x1', 'x2', 'x3', 'x4' ]
a: x2 , b: x1
a: x3 , b: x2
a: x3 , b: x2
a: x3 , b: x1
a: x4 , b: x3
a: x4 , b: x2
After sort: [ 'x1', 'x3', 'x2', 'x4' ]

The logic doesnt work (x4 needs to be before x1 as mentioned in the 1st item of order array) because the x1,x4 pair is never directly compared by sort.

Looking for suggestions.

EXPECTED RESULT: [ 'x4', 'x3', 'x2', 'x1' ] ==> x4 must come before x1 [order array - item 1]

OR ["x4", "x1", "x3", "x2"] ==> satisfies all the rules from order array i,e x3 is before x2 & x4 is before x1

NOTE: The order array may have variable number of rows with variable items within each row. If conflicting sort order is specified by multiple rows, then the sort order provided by the row that at lower index applies.

arrays javascript
3 Answers

Here's a simple implementation of topological sorting using the depth-first walk. Isolated nodes are added in the reversed order.

function topsort(nodes, graph) {
    let color = {},
        sorted = [];

    for (let node of nodes)
        visit(node)

    return sorted

    function visit(node) {
        if (color[node] === 'black')
            return
        if (color[node] === 'grey')
            throw new Error('cycle!')
        color[node] = 'grey'
        for (let [n, m] of graph)
            if (n === node)
                visit(m)
        color[node] = 'black'
        sorted.unshift(node)
    }
}

//

let data = [...'abcdefgh'];

let order = [
    ['b', 'a'],
    ['a', 'c'],
    ['a', 'g'],
    ['f', 'c'],
    ['e', 'f'],
];


console.log(...topsort(data, order))

user_9891210

You can achieve that using Topological Sort - Kahn’s Algorithm, pseudo code:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is not empty do
    remove a node n from S
    add n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else 
    return L   (a topologically sorted order)

JavaScript implementations (Kahn’s Algorithm):

const topologySort = (arr, rules) => {
  class Graph {
      constructor() {
          this.adjacencyList = {}
      }
      addVertex(vertex) {
          if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []
      }
      addEdge(v1, v2) {
          this.adjacencyList[v1].push(v2)
      }
  }

  const graph = new Graph()

  arr.forEach(v => graph.addVertex(v))
  rules.forEach(e => graph.addEdge(...e))

  const vertices = Object.keys(graph.adjacencyList)
  const inDegree = {}
  for (const v of vertices) {
      for (neighbor of graph.adjacencyList[v]) {
          inDegree[neighbor] = inDegree[neighbor] + 1 || 1
      }
  }

  const queue = vertices.filter(v => !inDegree[v])
  const topNums = {}
  let index = 0
  while (queue.length) {
      const v = queue.shift()
      topNums[v] = index++
      for (const neighbor of graph.adjacencyList[v]) {
          inDegree[neighbor]--
          if (inDegree[neighbor] === 0) {
              queue.push(neighbor)
          }
      }
  }

  if (index !== vertices.length) console.log('* Detect cycle in graph. Check your order rules. *')
  
  return Object.keys(topNums)
}

const data = ['x1', 'x2', 'x4', 'x3', 'x5', 'x6']

console.log('--- With correct order rules ---')
const correctOrder = [['x4', 'x1'], ['x3', 'x2'], ['x6', 'x1']]
const correctRes = topologySort(data, correctOrder)
console.log(...correctRes)

console.log('--- With incorrect order rules [x1 and x6 creating a cycle]---')
const incorrectOrder = [['x4', 'x1'], ['x3', 'x2'], ['x6', 'x1'], ['x1', 'x6']]
const cycledRes = topologySort(data, incorrectOrder)
console.log(...cycledRes)

user_49837520

As others have mentioned, this is a case of topological sorting.

Here is a solution that also works when the input array has duplicate values:

function topologicalRanking(order) {
    // Build adjacency list
    let adj = {};
    for (let [a, b] of order) {
        adj[a] ??= [];
        (adj[b] ??= []).push(a);
    }
    // Implementation of https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search:
    let rank = {};
    let nextRank = 1;
    Object.keys(adj).map(function dfs(node) {
        if (rank[node] > 0) return;
        if (rank[node]) throw new Error("cycle detected");
        rank[node] = -1;
        adj[node].forEach(dfs);
        rank[node] = nextRank++;
    });
    return rank;
}

function bucketSort(arr, rank) {
    buckets = [];
    for (let value of arr) (buckets[rank[value] || 0] ??= []).push(value);
    return buckets.flat();
}

// Example run, with duplicates in data
let order = [['x4', 'x1'],['x3', 'x2'],['x0', 'x2']];    
let data = ['x1', 'x2', 'x4', 'x5', 'x0', 'x2', 'x3', 'x3', 'x1', 'x6'];

data = bucketSort(data, topologicalRanking(order));

console.log(data);

user_54598390
Related