Sorting a php array of arrays by custom order
PhpArraysMultidimensional ArraySortingPhp Problem Overview
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.
Php Solutions
Solution 1 - Php
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 - Php
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 - Php
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 - Php
Without sort you also can get it.
-
If there are no duplicate ids and
$ordercontains allidvalues from$arrayand theidcolumn in$arraycontains all values in$order, you can achieve the same result by flipping the values into keys in$order, then assign temporary first level keys to array, then either merge or replace$arrayinto$order.$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'), ); $order = array_flip($order); $array = array_column($array,null,"id"); $result = array_replace($order,$array); var_dump(array_values($result)); -
With potentially duplicate ids in
$array:$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'), ); $order_dict = array_flip($order); $order_dict = array_combine($order, array_fill(0, count($order), [])); foreach($array as $item){ $order_dict[$item["id"]][] = $item; } //$order_dict = array_filter($order_dict); // if there is empty item on some id in $order array $result = []; foreach($order_dict as $items){ foreach($items as $item){ $result[] = $item; } } var_dump($result);
Solution 5 - Php
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 advancefastsort
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');
Solution 6 - Php
You need to define your own comparison function and use usort or uasort if you want to maintain index association.
Solution 7 - Php
@salathe For those of you that are having a hard time understanding what salathe's usort is doing:
Each item in $array is a 'champion' in a tournament to be at the start of a new array (except instead of being number one they want to be number 0).
$a is the home champion, and $b the opponent champion in a match.
$pos_a and $pos_b from the callback are what attributes will be used in the fight for champion a and b. In this case this attribute is the index of the champions id in $order.
Then there is the fight at the return. Now we look to see if having more or less of the attribute is better. In a usort battle the home champion wants a negative number so he can be sooner in the array. The away champion wants a positive number. And should there be a 0 it is a tie.
So following this analogy when away champions attribute(index in $order) is subtracted from the home teams attribute, the larger the away champions attribute is the less likely it is to win by getting a positive number. However if you were to reverse the way the attributes are used, now home champion's attribute is subtracted from away champion's. In this case a larger number for the away champion is more likely to make him have the match end in a positive number.
Code would look like:
note: code is run many times much like a real tournament has many battles in order to decide who gets first(ie 0 / start of array)
//tournament with goal to be first in array
usort($champions, function ($home, $away) use ($order) {
$home_attribute = array_search($a['id'], $order);
$away_attribute = array_search($b['id'], $order);
//fight with desired outcome for home being negative and away desiring positive
return $home_attribute - $away_attribute;
});