Здравствуйте. Подскажите пожалуйста алгоритм или php код для сортировки иерархического массива. 

Есть массив в котором хранятся id и parent_id, нужно его отсортировать так, чтобы он в порядке иерархии и имел новый ключ level, где хранился бы уровень вложенности. Желательно без рекурсии и дополнительных библиотек.


Структура отсортированного массива была бы приблизительно такая:

исходный массив надо придумать?
сначала построй "дерево"
, чтоб вложенные элементы действительно ставли вложенными и неважно, что струкутра усложнится(на поле "дети текущего элемента") и станет отличаться от целевой - потом поправим.
а потом проходимся по всему массиву при помощи array_walk_recursive. c учетом того, что array_walk_recursive возвращает только false или true, то даю идею:
а) хранить "плоский" массив и передавать его в callback-функцию не через третий параметрй($userdata), а в виде статической переменной внутри самой фунцкии
б) возвращать значение этой самой статической переменной, если первые два параметра null(признак "запуска функции вручную" - вме вызова walk_array_recursive)

хотя мне кажется, что вывод при передаче null/null - это изврат

Добавлено через 6 минут и 25 секунд
впрочем, я всю усложнил. ща попроще решение набросаю.

значит, более простой вариант. назовем наш массив $_source
первым делом надо сделать так, чтоб ключом элемента массива был его id.
после чего заполнить поле level:
0. заполняем поле level для всех элементов значением null(чтоб определить, где )
1. если родительского элемента нет(!isset($_source[$currentElement['parent']])), то устанавливаем у текущего элемента поле level = 0
2. если родительский элемент есть, то берем его уровень(если он не null - то есть уже рассчитан), добавляем 1 и получаем уровень текущего элемента
3. проходим по массиву, выполняя пункт 2 до тех пор, пока значения не перестанут меняться.
4. выбрасываем элементы с level = null - у этих элементов указан не существующий parent
полученный массив можно отсортировать при помощи usort. callback функция будет реализовывать следующую логику сравнения элементов $el1 и $el2:
0. если $el1['level'] == $el2['level'] && $el1['parent'] == $el2['parent'], то вернуть сравнение $el1['id'] и $el2['id']("1" если $el1['id'] больше, "0" если равны и "-1" если меньше)
1. если уровни одинаковы, но parent разные, то выполнить сравнение для parent-элементов и это же значение вернуть как сравнение текущих элементов.
2. если уровни разные, то вернуть сравнение элемента с меньшим уровнем и родителя элемента с большим уровнем.

А в чём преступление если прибегнуть к рекурсии? Вобще рекурсивный алогоритм можно представить в виде обычного цикла с ручным стеком. Если не так принципиально примерно так (вобще форма хранения неудобная, приходится мапить дерево в промежуточную структуру, чтобы потом лишний раз его не перебирать):


Это сообщение отредактировал(а) segrey - 31.12.2009, 23:38