3
$\begingroup$

I have an array of objects, each of them has a numeric id and another array attached to them.

The array in the object contains the dependencies of that object. Each dependency is an id from the other objects. There are no circular dependencies.

Let's take this diagram:

enter image description here

The ids of the objects are in the upper rectangle, the dependecies are in the lower one.

I need to sort the array in a way, so if an object depends on another object, then it needs to be after that object in the array.

So for the example above it would be 

3 1 2 4
Improve this question
$\endgroup$
  • $\begingroup$ Also, this is not homework $\endgroup$ – Bálint Jun 29 '16 at 16:14
  • 1
    $\begingroup$ You're looking for topological sort. $\endgroup$ – David Richerby Jun 29 '16 at 16:30
4
$\begingroup$

You effectively have a directed graph here, where your vertices are the entries of your array, and you have an edge $(i,j)$ between entries $i$ and $j$ iff $j$ depends on $i$. What you want is a topological sort of this graph (https://en.wikipedia.org/wiki/Topological_sorting).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.