Sort a list of articles by next article

Question

I know there are a lot of sort related issues but I can not find my solution.

I have data like this:

const list = [
  {
    name: 'one',
    next: 'two'
  },
  {
    name: 'three',
    next: 'four'
  },
  {
    name: 'four',
    next: 'five'
  },
  {
    name: 'two',
    next: 'three'
  },
]

And I want to classify them according to the next property.

I don't want to sort by alphabetical order. But by the next property.

If a.next === b.name then he come first.

I tried this :

list.sort((a, b) => {
 if (a.next === b.name) {
   return -1
 }
})

How can I achieve this ?

Result I want :

list = [
      {
        name: 'one',
        next: 'two'
      },
      {
        name: 'two',
        next: 'three'
      },
      {
        name: 'three',
        next: 'four'
      },
      {
        name: 'four',
        next: 'five'
      }
    ]

Is it guaranteed there is no cycle (which would make it impossible), no forking (which would have more than one solution) or whatever i forgot that makes this question underdefined? — ASDFGerte, Jul 02 '18 at 15:16
Is it me or the duplicate post is not really the same with this post? — Eddie, Jul 02 '18 at 15:19
It's not the same and I read it before to ask my question... @ASDFGerte I just want to sort this array. If `next.value = current.name` => next.value go next in the list. — uciska, Jul 02 '18 at 15:21

Eddie · Accepted Answer · 2018-07-02T16:04:24.747

Assuming the array is sortable based on the required logic. You can:

You can organize the array into an object using reduce. Get the first element by checking if the name does not exist as a next. Use the classic for to loop in the length of the array.

const list = [{"name":"one","next":"two"},{"name":"three","next":"four"},{"name":"four","next":"five"},{"name":"two","next":"three"}];

const order = list.reduce((c, v, i) => Object.assign(c, {[v.name]: v}), {}); //Make an order object. This will make it easier to get the values. Use the name as the key
let key = Object.keys(order).find(o => !list.some(x => x.next === o));  //Find the first element. Element that is not found on next

let result = [];
for (i = 0; i < list.length; i++) {  //Loop thru the array. Get the value from order object. 
  result.push(order[key]);           //Push the array from the object order
  key = order[key].next;             //overide the key with the next
}

console.log(result);

Thanks! That's exactly what I wanted. – uciska Jul 02 '18 at 16:06 — uciska, Jul 02 '18 at 16:06

Patrick Roberts · Answer 2 · 2018-07-02T16:26:36.237

1

Assuming that there are no cycles or forks in the chain, you can sort this list out-of-place in O(n) using the following function:

const list = [
  {
    name: 'one',
    next: 'two'
  },
  {
    name: 'three',
    next: 'four'
  },
  {
    name: 'four',
    next: 'five'
  },
  {
    name: 'two',
    next: 'three'
  }
]

function sortLinkedListBy(list, from, to) {
  // collect list of items into dictionary<name, <next, item>>
  // collect next keys into Set<string>
  const { map, set } = list.reduce(({ map, set }, item) => {
    const { [from]: name, [to]: next } = item
    map.set(name, { next, item })
    set.add(next)
    return { map, set}
  }, { map: new Map(), set: new Set() })
  // locate single name that does not exist in set of next keys
  const [key] = Array.from(map.keys()).filter(key => !set.has(key))
  // reduce list (to iterate same amount of times as number of items)
  // accumulator is a tuplet containing sorted list and next key in chain
  const { list: sorted } = list.reduce(({ list, key: name }) => {
    const { next, item } = map.get(name)
    list.push(item)
    return { list, key: next }
  }, { list: [], key })

  return sorted
}

console.log(sortLinkedListBy(list, 'name', 'next'))

edited Jul 02 '18 at 16:26

answered Jul 02 '18 at 15:45

Patrick Roberts

49,224
10
102
153

Thanks! It's a little complicated for me. I will take the time to understand each line. – uciska Jul 02 '18 at 16:08
It's essentially the same steps as the other answer, just posted earlier and encapsulated in a modular function... Also in the other answer, the use of `.find( ... .some() )` makes the time complexity O(n^2) while this one is O(n) – Patrick Roberts Jul 02 '18 at 16:08
@uciska I added some comments since that seems to be what you're wanting. `.reduce()` and `.filter()` are both O(n) and since there are no O(n) calls in any of them, the total time complexity is therefore O(n) as well. – Patrick Roberts Jul 02 '18 at 16:15
Thanks you're awesome ! – uciska Jul 02 '18 at 16:26

Sort a list of articles by next article

2 Answers2