Sort array values based on parent/child relationship

Question

I am trying to sort an array to ensure that the parent of any item always exists before it in the array. For example:

Array
(
    [0] => Array
        (
            [0] => 207306
            [1] => Bob
            [2] => 
        )

    [1] => Array
        (
            [0] => 199730
            [1] => Sam
            [2] => 199714
        )

    [2] => Array
        (
            [0] => 199728
            [1] => Simon
            [2] => 207306
        )

    [3] => Array
        (
            [0] => 199714
            [1] => John
            [2] => 207306
        )

    [4] => Array
        (
            [0] => 199716
            [1] => Tom
            [2] => 199718
        )

    [5] => Array
        (
            [0] => 199718
            [1] => Phillip
            [2] => 207306
        )

    [6] => Array
        (
            [0] => 199720
            [1] => James
            [2] => 207306
        )

)

In the above array this "fails" as [1][2] (Sam) does not yet exist and nor does [4][2] (Tom).

The correct output would be as, in this case, as both Sam and Tom's parents already exist before they appear in the array:

Array
(
    [0] => Array
        (
            [0] => 207306
            [1] => Bob
            [2] => 
        )

    [1] => Array
        (
            [0] => 199714
            [1] => John
            [2] => 207306
        )


    [2] => Array
        (
            [0] => 199730
            [1] => Sam
            [2] => 199714
        )

    [3] => Array
        (
            [0] => 199728
            [1] => Simon
            [2] => 207306
        )


    [4] => Array
        (
            [0] => 199718
            [1] => Phillip
            [2] => 207306
        )


    [5] => Array
        (
            [0] => 199716
            [1] => Tom
            [2] => 199718
        )

    [6] => Array
        (
            [0] => 199720
            [1] => James
            [2] => 207306
        )

)

I found an answer https://stackoverflow.com/a/12961400/1278201 which was very close but it only seems to go one level deep (i.e. there is only ever one parent) whereas in my case there could be 1 or 10 levels deep in the hierarchy.

How do I sort the array so no value can appear unless its parent already exists before it?

Answer 1

This will trivially order the array (in O(n)) putting first all those with no parent, then these whose parent is already in the array, iteratively, until there's no children having the current element as parent.

# map the children by parent
$parents = ['' => []];
foreach ($array as $val) {
    $parents[$val[2]][] = $val;
}
# start with those with no parent
$sorted = $parents[''];
# add the children the current nodes are parent of until the array is empty
foreach ($sorted as &$val) {
    if (isset($parents[$val[0]])) {
        foreach ($parents[$val[0]] as $next) {
            $sorted[] = $next;
        }
    }
}

This code requires PHP 7, it may not work in some cases under PHP 5. - for PHP 5 compatibility you will have to swap the foreach ($sorted as &$val) with for ($val = reset($sorted); $val; $val = next($sorted)):

# a bit slower loop which works in all versions
for ($val = reset($sorted); $val; $val = next($sorted)) {
    if (isset($parents[$val[0]])) {
        foreach ($parents[$val[0]] as $next) {
            $sorted[] = $next;
        }
    }
}

Live demo: https://3v4l.org/Uk6Gs

Answer 2

I have two different version for you.

a) Using a "walk the tree" approach with recursion and references to minimize memory consumption

$data = [
    [207306,'Bob',''], [199730,'Sam',199714],
    [199728,'Simon',207306], [199714,'John',207306],
    [199716, 'Tom',199718], [199718,'Phillip',207306],
    [199720,'James',207306]
];

$list = [];
generateList($data, '', $list);

var_dump($list);

function generateList($data, $id, &$list) {
    foreach($data as $d) {
        if($d[2] == $id) {          
            $list[] = $d; // Child found, add it to list            
            generateList($data, $d[0], $list); // Now search for childs of this child
        }
    }
}

b) Using phps built in uusort()function (seems only to work up to php 5.x and not with php7+)

$data = [
    [207306,'Bob',''], [199730,'Sam',199714],
    [199728,'Simon',207306], [199714,'John',207306],
    [199716, 'Tom',199718], [199718,'Phillip',207306],
    [199720,'James',207306]
];

usort($data, 'cmp');

var_dump($data);

function cmp($a, $b) {  
    if($a[2] == '' || $a[0] == $b[2]) return -1; //$a is root element or $b is child of $a
    if($b[2] == '' || $b[0] == $a[2]) return 1; //$b is root element or $a is child of $b
    return 0; // both elements have no direct relation
}

Answer 3

I checked this works in PHP 5.6 and PHP 7

Sample array:

$array = Array(0 => Array(
        0 => 207306,
        1 => 'Bob',
        2 => '',
    ),
    1 => Array
        (
        0 => 199730,
        1 => 'Sam',
        2 => 199714,
    ),
    2 => Array
        (
        0 => 199728,
        1 => 'Simon',
        2 => 207306,
    ),
    3 => Array
        (
        0 => 199714,
        1 => 'John',
        2 => 207306,
    ),
    4 => Array
        (
        0 => 199716,
        1 => 'Tom',
        2 => 199718,
    ),
    5 => Array
        (
        0 => 199718,
        1 => 'Phillip',
        2 => 207306,
    ),
    6 => Array
        (
        0 => 199720,
        1 => 'James',
        2 => 207306,
    ),
); 



echo "<pre>";
$emp = array();

//form the array with parent and child
foreach ($array as $val) {
    $manager = ($val[2] == '') ? 0 : $val[2];
    $exist = array_search_key($val[2], $emp);
    if ($exist)
        $emp[$exist[0]][$val[0]] = $val;
    else
    //print_R(array_search_key(199714,$emp));
        $emp[$manager][$val[0]] = $val;
}

$u_emp = $emp[0];
unset($emp[0]);

//associate the correct child/emp after the manager
foreach ($emp as $k => $val) {
    $exist = array_search_key($k, $u_emp);
    $pos = array_search($k, array_keys($u_emp));

    $u_emp = array_slice($u_emp, 0, $pos+1, true) +
            $val +
            array_slice($u_emp, $pos-1, count($u_emp) - 1, true);

}
print_R($u_emp); //print the final result

// key search function from the array
function array_search_key($needle_key, $array, $parent = array())
{
    foreach ($array AS $key => $value) {
        $parent = array();
        if ($key == $needle_key)
            return $parent;
        if (is_array($value)) {
            array_push($parent, $key);
            if (($result = array_search_key($needle_key, $value, $parent)) !== false)
                return $parent;
        }
    }
    return false;
}

Answer 4

Find the below code that might be helpful.So, your output is stored in $sortedarray.

$a=array(array(207306,'Bob',''),
array (199730,'Sam',199714),
array(199728,'Simon',207306),
array(199714,'John',207306),
array(199716,'Tom',199718),
array(199718,'Phillip',207306),
array(199720,'James',207306));

$sortedarray=$a;
foreach($a as $key=>$value){
    $checkvalue=$value[2];
    $checkkey=$key;
foreach($a as $key2=>$value2){
    if($key<$key2){
            if ($value2[0]===$checkvalue){
                $sortedarray[$key]=$value2;
                $sortedarray[$key2]=$value;
        }else{
            }
    }
  }
 }

 print_r($sortedarray);