Sorting 2d array rows by one column, then where column is equal to another column, then by the other column

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 its parent.

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

I'm wondering what is the easiest solution to achieve this. I've managed to do that, but I can't 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 an easier way to achieve it?

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!

Answer 2

<?php

$arr = [
    ['id' => 15, 'parent' => 12],
    ['id' => 10, 'parent' => 12],
    ['id' => 12, 'parent' => 12],
    ['id' => 17, 'parent' => 12],
    ['id' => 21, 'parent' => 15],
    ['id' => 13, 'parent' => 15],
    ['id' => 15, 'parent' => 0],
    ['id' => 25, 'parent' => 15],
    ['id' => 7,  'parent' => 0],
    ['id' => 18, 'parent' => 7],
    ['id' => 4,  'parent' => 7],
    ['id' => 1,  'parent' => 3],
    ['id' => 5,  'parent' => 5],
    ['id' => 2,  'parent' => 7],
];

//sort by parent id and add child below parent
usort($arr, function ($a, $b) {
    //both root parents
    if ($a['parent'] == 0  && $b['parent'] == 0) {
        if ($a['id'] < $b['id']) return -1; else return 1;
    }

    //both have same parent
    if ($a['parent'] == $b['parent']) {
        if ($a['id'] < $b['id']) return -1; else return 1;
    }
    
    //both child with different parents
    if ($a['parent'] != 0  && $b['parent'] != 0) {
        if ($a['parent'] < $b['parent']) return -1; else return 1;
    }

    //a has parent bigger then b id
    if ($a['parent'] != 0) {
        if ($a['parent'] < $b['id']) return -1; else return 1;
    }
    
    //b has parent bigger then a id
    if ($b['parent'] != 0) {
        if ($b['parent'] < $a['id']) return 1; else return -1;
    }
    
    return 0;
});

?>      

Answer 3

You have 3 rules to enforce while sorting:

1. Position lower parented rows before higher parented rows, then
2. Position rows with equal id and parent values before the opposite, then
3. Position lower id'ed rows before higher id'ed rows.

Code: (Demo)

usort(
    $array,
    fn($a, $b) =>
        [$a['parent'], $a['id'] !== $a['parent'], $a['id']]
        <=>
        [$b['parent'], $b['id'] !== $b['parent'], $b['id']]
);
var_export($array);

P.s. I find it to be a bit of a code smell to have a row where the id is the same as its parent. I think if an id is the top level parent, then its parent should be 0 or null.