How to sort an array with elements depending on each other?

Question

Algorithms

View array

[
  [
    "name1" => ["value" => "v", "depends" => ["name3, name 5"]
  ],
  [
    "name2" => ["value" => "v", "depends" => ["name1"]
  ],
  [
    "name3" => ["value" => "v", "depends" => ["name5"]
  ],
  [
    "name4" => ["value" => "v", "depends" => ["name1, name 2"]
  ],
  [
    "name5" => ["value" => "v", "depends" => []
  ],
]

Bring to mind

[
  [
    "name5" => ["value" => "v", "depends" => []
  ],
  [
    "name3" => ["value" => "v", "depends" => ["name5"]
  ],
  [
    "name1" => ["value" => "v", "depends" => ["name3, name 5"]
  ],
  [
    "name2" => ["value" => "v", "depends" => ["name1"]
  ],
  [
    "name4" => ["value" => "v", "depends" => ["name1, name 2"]
  ],
]

How to do it right?

Answer 1

This is the so-called "topological sort". It is done through sequential depth-first search, starting with all possible elements.

алг recurse(поссылке x : элемент, поссылке результат : список)
  если x.метка = чёрный
    возврат
  если x.метка = серый
    стоп ("найдена циклическая зависимость")
  x.метка := серый
  для всех y : зависимых от x
    recurse(y)
  x.метка := чёрный
  результат.добавить(x)

алг main()
  для всех x : массив
    x.метка := белый
  result := []
  для всех x : массив
    recurse(x, result)

In short: we perform a standard depth-first search, starting with all elements, and on exit, we add the element to the list.