CODEWITHSUNDEEP
javascriptalgorithmsorting
uciska
uciska

Reputation: 302

Sort a list of articles by next article

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'
      }
    ]

Upvotes: 2

Views: 94

Answers (2)

Patrick Roberts
Patrick Roberts

Reputation: 51936

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'))

Upvotes: 1

Eddie
Eddie

Reputation: 26844

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);

Upvotes: 4

Related Questions