How to sort an array of arrays of strings in js?

Question

JavaScript

You need to build an array like this:

[['butter', 'jelly'], ['bananas', 'apples'], ['peanuts', 'butter'], ['jelly', 'bananas']]

Here in this sequence:

[['peanuts', 'butter'], ['butter', 'jelly'], ['jelly', 'bananas'], ['bananas', 'apples']]

That is, it is necessary that every second element of the array matches the first element of the next array.

Here is the code that works, but not always (not for all cases):

routes.sort(([a, b], [c, d]) => {
     return b === c ? -1 : a === d ? 1 : 0 
})

I think more conditions need to be added. In general, the algorithm is associated with directed graphs and in adult languages ​​it is solved using HashMap and reversed Hash Map, however, in JS, the sorting option seems to be the most concise (efficiency does not matter)

Answer 1

This problem, in principle, cannot be solved by sorting, since sorting is about the ratio greater than/less than/equal to, which is not present in this case.
The simplest thing here is to build a doubly linked list from these elements, and then convert it to the resulting array:

function orderArray(arr) {
  // для начала построим ноды списка и соберем их в 2 HashMap по обоим строкам
  const maps = arr.reduce((acc, item) => {
    const node = {item, next: null, prev: null};
    acc[0][item[0]] = node;
    acc[1][item[1]] = node;
    return acc;
  }, [{}, {}]);

  // после пройдемся по обоим HashMap и соединим связи
  for(const key of Object.keys(maps[0])) {
    maps[0][key].next = maps[0][maps[0][key].item[1]] || null;
  }
  for(const key of Object.keys(maps[1])) {
    maps[1][key].prev = maps[1][maps[1][key].item[0]] || null;
  }

  // найдем начальную ноду списка (ноду без предыдущей ноды)
  let cur = Object.values(maps[0]).find(({prev}) => prev === null);

  // и начиная с нее соберем список в массив
  const result = [];
  while(cur) {
    result.push(cur.item);
    cur = cur.next;
  }

  return result;
}

console.log(orderArray([['butter', 'jelly'], ['bananas', 'apples'], ['peanuts', 'butter'], ['jelly', 'bananas']]));

Answer 2

Since this is the case, Dmitry Belyaev , Roman , rate it.)

(() => {
  const orderArray = (arr) => {
    const itemsForMap = arr.map((items) => ([items[0], { items, prev: undefined }]))
    const itemsMap = new Map(itemsForMap);

    let last;
    itemsMap.forEach((node) => {
      const next = itemsMap.get(node.items[1]);
      if(next) {
        next.prev = node;
      }
      else {
        last = node;
      }
    });

    const result = [];
    result.length = arr.length;

    let current = last;
    for(let i = result.length - 1; i > -1; i--) {
      result[i] = current.items;
      current = current.prev;
    }

    return result;
  };
  
  return orderArray([['butter', 'jelly'], ['bananas', 'apples'], ['peanuts', 'butter'], ['jelly', 'bananas']]);
})()

Everything seems to be true, but I wrote this at 7 in the morning before going to bed ...