Sorting array depending on parent; a tree in a one-dimensional array

Question

How can I sort an array with all children after their respective parents? I guess I'm trying to store a tree inside a one-dimensional array. I have tried to figure this out using usort, but I don't think it is the right tool for the job.

Example input array:

array (0 => array ( 'id' => '1', 'parent' => '0', ), 
1 => array ( 'id' => '2', 'parent' => '1', ), 
2 => array ( 'id' => '3', 'parent' => '0', ), 
3 => array ( 'id' => '5', 'parent' => '0', ), 
4 => array ( 'id' => '17', 'parent' => '3', ), 
5 => array ( 'id' => '31', 'parent' => '2', ), 
6 => array ( 'id' => '32', 'parent' => '2', ))

Example output:

Answer 1

Start by building an actual tree, then flatten that tree:

$array = array (0 => array ( 'id' => '1', 'parent' => '0', ),
                1 => array ( 'id' => '2', 'parent' => '1', ),
                2 => array ( 'id' => '3', 'parent' => '0', ),
                3 => array ( 'id' => '5', 'parent' => '0', ),
                4 => array ( 'id' => '17', 'parent' => '3', ),
                5 => array ( 'id' => '31', 'parent' => '2', ),
                6 => array ( 'id' => '32', 'parent' => '2', ));

/* Building a tree. We also save a map of references to avoid                                
   searching the tree for nodes */

//Helper to create nodes                                                                     
$tree_node = function($id, $parent) {
  return array('id' => $id, 'parent' => $parent, 'children' => array());
};

$tree = $tree_node(0, null); //root node                                                     
$map = array(0 => &$tree);
foreach($array as $cur) {
  $id = (int) $cur['id'];
  $parentId = (int) $cur['parent'];
  $map[$id] =& $map[$parentId]['children'][];
  $map[$id] = $tree_node($id, $parentId);
}

//Now recursively flatten the tree:                                                          
function flatter($node) {
  //Create an array element of the node                                            
  $array_element = array('id' => (string) $node['id'],
                         'parent' => (string) $node['parent']);
  //Add all children after me                                                                
  $result = array($array_element);
  foreach($node['children'] as $child) {
    $result = array_merge($result, flatter($child));
  }
  return $result;
}

$array = flatter($tree);
array_shift($array); //Remove the root node, which was only added as a helper                

print_r($array);