按id和父排序php数组

Question

I have an array of arrays - each has own id and parent id values. I want to sort it so that every child should be beneath it's parent. Let me show You my code:

Given Array:

$arr = array(array('id' => 15, 'parent' => 12), 
array('id' => 10, 'parent' => 12), 
array('id' => 12, 'parent' => 12), 
array('id' => 17, 'parent' => 12), 
array('id' => 21, 'parent' => 15), 
array('id' => 13, 'parent' => 15), 
array('id' => 15, 'parent' => 15), 
array('id' => 25, 'parent' => 15), 
array('id' => 7, 'parent' => 7), 
array('id' => 18, 'parent' => 7), 
array('id' => 4, 'parent' => 7), 
array('id' => 1, 'parent' => 3), 
array('id' => 5, 'parent' => 5), 
array('id' => 2, 'parent' => 7));

How the output should look like (asc by parents, every children also ascending - always under parent (parent always as first!!!)):

      0 =>
          'id' => int 1
          'parent' => int 3
      1 =>
          'id' => int 5
          'parent' => int 5
      2 =>
          'id' => int 7
          'parent' => int 7
      3 =>
          'id' => int 2
          'parent' => int 7
      4 =>
          'id' => int 4
          'parent' => int 7
      5 =>
          'id' => int 18
          'parent' => int 7
      6 =>
          'id' => int 12
          'parent' => int 12
      7 =>
          'id' => int 10
          'parent' => int 12
      8 =>
          'id' => int 15
          'parent' => int 12
      9 =>
          'id' => int 17
          'parent' => int 12
      10 =>
          'id' => int 15
          'parent' => int 15
      11 =>
          'id' => int 13
          'parent' => int 15
      12 =>
          'id' => int 21
          'parent' => int 15
      13 =>
          'id' => int 25
          'parent' => int 15

Question: I'am wondering what is the easiest solution to achieve this ? I've managed to do that, but I cant stop the feeling that there is a way to do that in quicker and more optimal way..

Here is my code:

function groupByParent ($array)
{
    $groups = array();
    foreach ($array as $a) {
        $groups[$a['parent']][] = $a;
    }
    return $groups;
}
function insideSort ($array)
{
    foreach ($array as $k => $v) {
        usort($array[$k], function($a, $b){
           return $a['id'] == $b['parent'] ? -1 : 1;
        });
        $f = array_shift($array[$k]);
        sort($array[$k]);
        array_unshift($array[$k], $f);
    }
    return $array;
}
function finalSort($array)
{
    $final = array();
    foreach ($array as $a) {
        $final = array_merge($final, $a);
    }
    return $final;
}

$grr = groupByParent($arr);
$irr = insideSort($grr);
ksort($irr);
$res = finalSort($irr);

Is there easier way to achieve it ?

Cheers

Answer 1

Explanation

Another way to sort the array, could be iterating through all elements in the array, and find all distinct parents, then store all siblings for each parent found, except for the once that has id same as parent. Then we sort it ascending and prepend the node that has id same as parent, to the start of the array.

Big O notation

The run time for this algorithm will have a best case of O(n), and a worst case of O(n^2).

Code

<?php

$arr = array(
    array('id' => 15, 'parent' => 12), 
    array('id' => 10, 'parent' => 12), 
    array('id' => 12, 'parent' => 12), 
    array('id' => 17, 'parent' => 12), 
    array('id' => 21, 'parent' => 15), 
    array('id' => 13, 'parent' => 15), 
    array('id' => 15, 'parent' => 15), 
    array('id' => 25, 'parent' => 15), 
    array('id' => 7, 'parent' => 7), 
    array('id' => 18, 'parent' => 7), 
    array('id' => 4, 'parent' => 7), 
    array('id' => 1, 'parent' => 3), 
    array('id' => 5, 'parent' => 5), 
    array('id' => 2, 'parent' => 7)
);

/* Declare variables */
$result = array();
$temp = array();
$parents = array();

/* Get all distinct parents and sort ascending */
for ($i = 0; $i < count($arr); $i++)
    if (!isset($temp[$arr[$i]['parent']]))
        $temp[$arr[$i]['parent']] = array();

ksort($temp);

/* Find all siblings with same parent */
for ($i = 0; $i < count($arr); $i++)
    if ($arr[$i]['parent'] === $arr[$i]['id'])
        $parents[] = $arr[$i]['parent'];
    else
        $temp[$arr[$i]['parent']][$arr[$i]['id']] = true;

/* Sort siblings ascending */
foreach ($temp as $key => $value)
    ksort($temp[$key]);

/* Prepend node where id is same as parent if existing */
for ($i = 0; $i < count($parents); $i++)
    $temp[$parents[$i]] = array($parents[$i] => true) + $temp[$parents[$i]];

/* Display properly */
foreach ($temp as $key => $value)
    foreach ($temp[$key] as $subKey => $subValue)
        $result[] = array('id' => $subKey, 'parent' => $key);

/* Output */
print_r($result);

?>

Execution time

Execution time for my code:
Execution 1: 0.00018095970153809
Execution 2: 0.00018692016601562
Execution 3: 0.00022411346435547
Execution 4: 0.00018596649169922
Execution 5: 0.00018620491027832
Execution 6: 0.00018501281738281
Execution 7: 0.00018501281738281
Execution 8: 0.00018596649169922
Execution 9: 0.00018095970153809
Execution 10: 0.00020003318786621

Average: 0.00019011497

Execution time for your code:
Execution 1: 0.00019311904907227
Execution 2: 0.0001978874206543
Execution 3: 0.00019693374633789
Execution 4: 0.0001981258392334
Execution 5: 0.0001990795135498
Execution 6: 0.00028491020202637
Execution 7: 0.00019598007202148
Execution 8: 0.00019693374633789
Execution 9: 0.0001978874206543
Execution 10: 0.00019717216491699

Average: 0.00020580291

Result was found using microtime(true) at top and bottom of code and subtracting the end time from the start time.

Conclusion

So the code I provided is not neccessarily an easier way to achieve what you want, however it looks like it's a little bit more efficient especially when using small arrays like the one in the code above.

I have not tested execution time on big arrays and would advice you to do so before choosing a solution.

And if you manage to figure out a way to get rid of the "Display properly" part (line 48-50 in my code) and instead store the data properly from start to end, the execution time would improve alot.

Good luck, and happy new year!