Sorting a php array of arrays by custom order
I have an array of arrays:
Array (
[0] => Array (
[id] = 7867867,
[title] = 'Some Title'),
[1] => Array (
[id] = 3452342,
[title] = 'Some Title'),
[2] => Array (
[id] = 1231233,
[title] = 'Some Title'),
[3] => Array (
[id] = 5867867,
[title] = 'Some Title')
)
The need to go in a specific order:
- 3452342
- 5867867
- 7867867
- 1231233
How would I go about doing that? I have sorted arrays before, and read plenty of other posts about it, but they are always comparison based (i.e. valueA < valueB).
Help is appreciated.
Solution 1:
You can use usort() to dictate precisely how the array is to be sorted. In this case, the $order array can be used within the comparison function.
The example below uses a closure to make life easier.
$order = array(3452342, 5867867, 7867867, 1231233);
$array = array(
array('id' => 7867867, 'title' => 'Some Title'),
array('id' => 3452342, 'title' => 'Some Title'),
array('id' => 1231233, 'title' => 'Some Title'),
array('id' => 5867867, 'title' => 'Some Title'),
);
usort($array, function ($a, $b) use ($order) {
$pos_a = array_search($a['id'], $order);
$pos_b = array_search($b['id'], $order);
return $pos_a - $pos_b;
});
var_dump($array);
The key to this working is having the values that are being compared, be the positions of the ids within the $order array.
The comparison function works by finding the positions of the ids of two items to be compared within the $order array. If $a['id'] comes before $b['id'] in the $order array, then the return value of the function will be negative ($a is less so "floats" to the top). If $a['id'] comes after $b['id'] then the function returns a positive number ($a is greater so "sinks" down).
Finally, there is no special reason for using a closure; it's just my go-to way of writing these sorts of throwaway functions quickly. It could equally use a normal, named function.
Solution 2:
Extending salathe's answer for this additional requirement:
Now what happens when I add items to the array and not to the sort? I don't care what order they appear, as long as it comes after the ones that I did specify.
You need to add two additional conditions in the sorting function:
- A "dont care" item must be considered greater than whitelisted items
- Two "dont care" items must be considered equal
So the revised code would be:
$order = array(
3452342,
5867867,
7867867,
1231233
);
$array = array(
array("id" => 7867867, "title" => "Must Be #3"),
array("id" => 3452342, "title" => "Must Be #1"),
array("id" => 1231233, "title" => "Must Be #4"),
array("id" => 5867867, "title" => "Must Be #2"),
array("id" => 1111111, "title" => "Dont Care #1"),
array("id" => 2222222, "title" => "Dont Care #2"),
array("id" => 3333333, "title" => "Dont Care #3"),
array("id" => 4444444, "title" => "Dont Care #4")
);
shuffle($array); // for testing
var_dump($array); // before
usort($array, function ($a, $b) use ($order) {
$a = array_search($a["id"], $order);
$b = array_search($b["id"], $order);
if ($a === false && $b === false) { // both items are dont cares
return 0; // a == b
} else if ($a === false) { // $a is a dont care
return 1; // $a > $b
} else if ($b === false) { // $b is a dont care
return -1; // $a < $b
} else {
return $a - $b; // sort $a and $b ascending
}
});
var_dump($array); // after
Output:
Before | After
-------------------------------+-------------------------------
array(8) { | array(8) {
[0]=> | [0]=>
array(2) { | array(2) {
["id"]=> | ["id"]=>
int(4444444) | int(3452342)
["title"]=> | ["title"]=>
string(12) "Dont Care #4" | string(10) "Must Be #1"
} | }
[1]=> | [1]=>
array(2) { | array(2) {
["id"]=> | ["id"]=>
int(3333333) | int(5867867)
["title"]=> | ["title"]=>
string(12) "Dont Care #3" | string(10) "Must Be #2"
} | }
[2]=> | [2]=>
array(2) { | array(2) {
["id"]=> | ["id"]=>
int(1231233) | int(7867867)
["title"]=> | ["title"]=>
string(10) "Must Be #4" | string(10) "Must Be #3"
} | }
[3]=> | [3]=>
array(2) { | array(2) {
["id"]=> | ["id"]=>
int(1111111) | int(1231233)
["title"]=> | ["title"]=>
string(12) "Dont Care #1" | string(10) "Must Be #4"
} | }
[4]=> | [4]=>
array(2) { | array(2) {
["id"]=> | ["id"]=>
int(5867867) | int(2222222)
["title"]=> | ["title"]=>
string(10) "Must Be #2" | string(12) "Dont Care #2"
} | }
[5]=> | [5]=>
array(2) { | array(2) {
["id"]=> | ["id"]=>
int(2222222) | int(1111111)
["title"]=> | ["title"]=>
string(12) "Dont Care #2" | string(12) "Dont Care #1"
} | }
[6]=> | [6]=>
array(2) { | array(2) {
["id"]=> | ["id"]=>
int(3452342) | int(3333333)
["title"]=> | ["title"]=>
string(10) "Must Be #1" | string(12) "Dont Care #3"
} | }
[7]=> | [7]=>
array(2) { | array(2) {
["id"]=> | ["id"]=>
int(7867867) | int(4444444)
["title"]=> | ["title"]=>
string(10) "Must Be #3" | string(12) "Dont Care #4"
} | }
} | }
Solution 3:
The other answers which are using methods with iterated calls of array_search() are not as efficient as they can be. By restructuring/flipping the "order" lookup array, you can completely omit all array_search() calls -- making your task much more efficient and brief. I'll use the most modern "spaceship operator" (<=>), but earlier techniques will work the same for the comparison line. The "null coalescing operator" (??) will act to check the existence of a given id value in the lookup array in the same way that isset() would -- this is always more efficient than array_search() or in_array().
Code: (Demo) (Demo with 7.4 arrow function syntax)
// restructure with values as keys, and keys as order (ASC)
$order = array_flip([3452342, 5867867, 7867867, 1231233]);
// generating $order = [3452342 => 0, 5867867 => 1, 7867867 => 2, 1231233 => 3];
$default = count($order);
// generating $default = 4
usort($array, function($a, $b) use($order, $default) {
return ($order[$a['id']] ?? $default) <=> ($order[$b['id']] ?? $default);
});
var_export($array);
Solution 4:
You need to define your own comparison function and use usort or uasort if you want to maintain index association.
Solution 5:
More Efficient Solution
$dict = array_flip($order);
$positions = array_map(function ($elem) use ($dict) { return $dict[$elem['id']] ?? INF; }, $array);
array_multisort($positions, $array);
Don't recalculate positions on every comparison
When your array is large or getting the id is costlier, using usort() can get bad, because you recalculate the id for each comparison. Try array_multisort() with pre-calculated positions (see mediumsort or fastsort in the example below), which isn't any more complicated.
Also searching for the id in the order array on each comparison (like in the accepted answer) doesn't improve performance, since you iterate over it every comparison. Calculate it once.
In the code snippet below you can see the main three sorting functions:
-
slowsort
The accepted answer. Searches the position on every comparison. -
mediumsort
Improvedslowsortby calculating the positions in advance -
fastsort
Improvedmediumsortby avoiding searching alltogher.
Note that these handle elements with an id not in given in the order by providing a fallback value of INF. If your order array matches the ids of the original array 1-to-1, then avoid sorting alltogether and just inserting the elements in the right position is the way to go. I added a function cheatsort that does exactly that.
You can more generally sort an array by a weight (see weightedsort in the example). Make sure to calculate the weight only once, to achieve good performance.
Performance (for an array of length 1000)
fastsort about 1 ms
mediumsort about 3 ms
slowsort about 60 ms
Hint: For larger arrays the difference gets worse.
Sorting Function Comparison
<?php
/**
* accepted answer
*
* re-evaluate position in order on each comparison
*/
function slowsort(&$array, $order, $key = 'id')
{
usort($array, function ($a, $b) use ($order, $key) {
$pos_a = array_search($a[$key], $order);
$pos_b = array_search($b[$key], $order);
return $pos_a - $pos_b;
});
}
/**
* calculate element positions once
*/
function mediumsort(&$array, $order, $key = 'id')
{
$positions = array_map(function ($elem) use ($order, $key) {
return array_search($elem[$key], $order);
}, $array);
array_multisort($positions, $array);
}
/**
* calculate positions without searching
*/
function fastsort(&$array, $order, $key = 'id')
{
$dict = array_flip($order);
$positions = array_map(function ($elem) use ($dict, $key) {
return $dict[$elem[$key]] ?? INF;
}, $array);
array_multisort($positions, $array);
}
/**
* when each order element gets used exactly once, insert elements directly
*/
function cheatsort(&$array, $order, $key = 'id')
{
$dict = array_flip($order);
$copy = $array;
foreach ($copy as $elem) {
$pos = $dict[$elem[$key]];
$array[$pos] = $elem;
}
}
/**
* Sort elements in $array by their weight given by $weight_func
*
* You could rewrite fastsort and mediumsort by replacing $position by a weight function
*/
function weightedsort(&$array, $weight_func)
{
$weights = array_map($weight_func, $array);
array_multisort($weights, $array);
}
/**
* MEASUREMENTS
*/
/**
* Generate the sorting problem
*/
function generate($size = 1000)
{
$order = array();
$array = array();
for ($i = 0; $i < $size; $i++) {
$id = random_int(0, PHP_INT_MAX);
$order[] = $id;
$array[] = array('id' => $id);
}
shuffle($order);
return [$array, $order];
}
/**
* Time $callable in ms
*/
function time_it($callable)
{
$then = microtime(true);
$callable();
$now = microtime(true);
return 1000 * ($now - $then);
}
/**
* Time a sort function with name $sort_func
*/
function time_sort($sort_func)
{
echo "Timing $sort_func", PHP_EOL;
[$array, $order] = generate();
echo time_it(function () use ($sort_func, &$array, $order) {
$sort_func($array, $order);
}) . ' ms' . PHP_EOL;
}
time_sort('cheatsort');
time_sort('fastsort');
time_sort('mediumsort');
time_sort('slowsort');