Как с помощью sort отсортировать объекты по совпадению ключ — значение?

Question

[AlexNew22]

Есть задача по сортировке билетом относительно цепочки их начала маршрута и до последнего города
Как это отсортировать с помощью sort?

const tickets = [
  {from: 'Sochi', to: 'Paris'},
  {from: 'Moscow', to: 'Sochi'},
  {from: 'London', to: 'Moscow'},
  {from: 'Berlin', to: 'Kamchatka'},
  {from: 'Paris', to: 'Berlin'},
]

Моя попытка

function sortTickets(tickets ) {
  return tickets.sort((a, b) => {
    return a.from === b.to
  })
}

Должна выйти такая последовательность в массиве

0: {from: 'London', to: 'Moscow'}
1: {from: 'Moscow', to: 'Sochi'}
2: {from: 'Sochi', to: 'Paris'}
3: {from: 'Paris', to: 'Berlin'}
4: {from: 'Berlin', to: 'Kamchatka'

Comments

[WbICHA]

a.from === a.to

Гениально.

[Alexandroppolus]

WbICHA, ещё и в колбэке для sort ))

[WbICHA]

Alexandroppolus, тогда можно ещё и мутацию упомянуть.)

[dollar]

Зачем здесь sort вообще?
За O(N) делаем два ассоциативных массива, и ещё за O(N) составляем цепочку.

Answer 1

[Сергей Соколов]

Топорное решение с временным свойством для сортировки.

Сначала найти самый первый город – тот, который есть только в from, но отсутствует в to. От него пляшем по цепочке, добавляя инкрементируемое свойство для сортировки.
Сортируем, и удаляем временное свойство.

const allFrom = tickets.map(item => item.from);
const allTo = tickets.map(item => item.to);
let city = allFrom.filter(item => !allTo.includes(item)).pop(); // первый город
const w = Symbol(); // чтобы случайно не затереть существующее свойство
let i = 0;
let ticket;
while (ticket = tickets.find(t => t.from === city)) {
  ticket[w] = i++;
  city = ticket.to;
}

// ура! сортировка!
tickets.sort((a, b) => a[w] - b[w]);

tickets.forEach(t => delete t[w]);

Answer 2

[Alexandroppolus]

function sortTickets(tickets) {
    const map = new Map();
    const transits = new Set();
    
    tickets.forEach((t) => {
        map.set(t.from, t);
        transits.add(t.to);
    });

    const start = tickets.find(t => !transits.has(t.from));

    const result = [];
    
    for (let t = start; t; t = map.get(t.to)) {
        result.push(t);
    }

    return result;
}

const sorted = sortTickets([
  {from: 'Sochi', to: 'Paris'},
  {from: 'Moscow', to: 'Sochi'},
  {from: 'London', to: 'Moscow'},
  {from: 'Berlin', to: 'Kamchatka'},
  {from: 'Paris', to: 'Berlin'},
]);

Comments

[Сергей Соколов]

хороший рефакторинг.
Но Т.С. мечтал о сортировке на Новый Год..

[Alexandroppolus]

Сергей Соколов, вряд ли мечтал осознанно, просто какая же сортировка без Math.sort )

вообще здесь требуется топологическая сортировка, только самый простой случай