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

<?php

/**
 * @author Prasath A.R
 * @copyright 2012
 * @Date 2012-8-31 17:14
 */

$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', ));

print_r($array);
echo "<br />";

for($i=0;$i<count($array);$i++)
{
for($j=$i;$j<count($array);$j++)
{
        if($array[$i]['parent']>$array[$j]['parent'])
        {
            $temp=$array[$i];
            $array[$i]=$array[$j];
            $array[$j]=$temp;
        }
    }
}

echo "<h2>After Sorting</h2><br />";
print_r($array);

?>

The Answer will be:

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
    )

)

After Sorting

Array ( [0] => Array ( [id] => 1 [parent] => 0 )

[1] => Array
    (
        [id] => 3
        [parent] => 0
    )

[2] => Array
    (
        [id] => 5
        [parent] => 0
    )

[3] => Array
    (
        [id] => 2
        [parent] => 1
    )

[4] => Array
    (
        [id] => 31
        [parent] => 2
    )

[5] => Array
    (
        [id] => 32
        [parent] => 2
    )

[6] => Array
    (
        [id] => 17
        [parent] => 3
    )

)

Answer 2

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);