0
$\begingroup$

I have a real world problem where I have a list of nodes. Each ones contains a name and the name of the node before it in order. I am trying to devise an algorithm to sort these in order. The problem is that any two random nodes will not tell me anything about their order unless they happen to lie next to each other, so I can't use a traditional sorting algorithm.

When I try to work through ideas everything basically comes down to "grab" the node at the start and then place it after the correct node" then repeat with the next node at start of the list. The problem is this has worse case running time of $O(n^2)$ complexity if the items are reversed. Any ideas of how to efficiently solve a problem like this?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Such has been called topological_sorting. $\endgroup$ Commented Jan 9, 2020 at 3:53
  • $\begingroup$ Just found there is a recent tag topological-ordering in addition to several Q&As. $\endgroup$ Commented Jan 9, 2020 at 3:59
  • $\begingroup$ I knew there had to be a name for it. Thanks $\endgroup$ Commented Jan 10, 2020 at 4:30

1 Answer 1

Reset to default
2
$\begingroup$

I believe you can solve it by:

  • first sorting the list that you have with some predictable ordering of the names. (maybe A -> Z)
  • Doing the final sort later, and to find the "previous" element thru name you just have to do a binary search on the ordered list.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.