Sorting a php array of arrays by custom order

Question

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:

1. 3452342
2. 5867867
3. 7867867
4. 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:

1. A "dont care" item must be considered greater than whitelisted items
2. 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

Without sort you also can get it.

1. If there are no duplicate ids and $order contains all id values from $array and the id column in $array contains 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 $array into $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));
   

2. 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

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
  Improved slowsort by calculating the positions in advance
• fastsort
  Improved mediumsort by 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');

View more solutions

Comments

[Honus Wagner]

Brilliant. Thanks. Now what happens when I add items to the array and not to the sort? Logically, I don't care what order they appear, as long as it comes after the ones that I did specify. How do I handle that?

[John]

Whats the best solution if I have an simple array: $array = (0=> values, 1=>values,2=>values,etc) by given array(5,2,4,1,3,0)?

[John]

Ok, after 5 seconds of research I found this: stackoverflow.com/questions/348410/… .

[Jason Basanese]

Hopefully this does not just further confuse people ;)

[Matt]

What if you want to sort by a key that doesn't have unique values? For instance if you sorted by Title but there could be multiple titles. It might be fine in this case, but there could be additional keys like date, or author.

[mickmackusa]

This partial solution came just 5 minutes after the question was posted. It is low-value because it is essentially only offering two hyperlinks to the manual and would be better placed as a comment. Over 5 years later, this answer is overshadowed by complete answers, rendering this post useless. Please consider removing. (Not going to downvote this post)

[mickmackusa]

I think this will only add confusion: "fight with desired outcome for home being negative and away desiring positive" I don't find that statement to be accurate at all.

[Neve12ende12]

Let's throw one more wrench into this problem. What if my array doesn't have array("id" => 5867867, "title" => "Must Be #2") but I still need array("id" => 7867867, "title" => "Must Be #3") to be #3 so I need #2 to be blank

[mickmackusa]

else if as two words is a violation of PSR-12 coding standards. In php, it should be one word: elseif.

[Kamel Mili]

what if one of them is nullable? like this id 7867867 doesn't exist but you still want to consider the order

[mickmackusa]

What is the point of array_flip() in 2. if you are immediately overwriting the variable on the next line. Why array_combine(array_fill())? Do you kean array_fill_keys()? The 2nd snippet is doing 6 iterating techniques -- would you do this in a real project?