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
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!