[ACCEPTED]-Sort array by object property in PHP?-sorting

The question was concerned about the inefficiency 44 of using usort because of the overhead of calling 43 the comparison callback. This answer looks 42 at the difference between using the built-in 41 sort functions and a non-recursive quicksort 40 implementation.

The answer changed over time 39 as PHP evolved since 2009, so I've kept 38 it updated. The older material, while no 37 longer relevant, is still interesting though!

TL;DR: as of php 7.0.1, a non-recursive quicksort is no longer faster than using usort with a callback. This 36 wasn't always the case, which is why the 35 details below make interesting reading. The 34 real takeaway is that if you benchmark your 33 problem and try alternative approaches, you 32 can come up with surprising results.

Jan 2016 update

Well 31 here we are with php 7.0 released and 7.1 30 on the way! Finally, for this dataset, the 29 built-in usort is ever-so-slightly faster!

+-----------+------------+------------+------------+------------+------------+
| Operation | HHVM       | php7.0.1   | php5.6.3   | 5.4.35     | 5.3.29     |
+-----------+------------+------------+------------+------------+------------+
| usort     | *0.0445    | *0.0139    |  0.1503    |  0.1388    |  0.2390    |
| quicksort |  0.0467    |  0.0140    | *0.0912    | *0.1190    | *0.1854    |
|           | 5% slower  | 1% slower  | 40% faster | 15% faster | 23% faster |
+-----------+------------+------------+------------+------------+------------+

Jan 2015 update

When I originally 28 answered this in 2009, I compared using 27 usort with a non-recursive quicksort to 26 see if there was a difference. As it turned 25 out, there was significant difference, with the quicksort 24 running 3x faster.

As it's now 2015, I thought 23 it might be useful to revisit this, so I 22 took code which sorts 15000 objects using 21 usort and quicksort and ran it on 3v4l.org 20 which runs it on lots of different PHP versions. The 19 full results are here: http://3v4l.org/WsEEQ

+-----------+------------+------------+------------+------------+------------+
| Operation | HHVM       | php7alpha1 | php5.6.3   | 5.4.35     | 5.3.29     |
+-----------+------------+------------+------------+------------+------------+
| usort     | *0.0678    |  0.0438    |  0.0934    |  0.1114    |  0.2330    |
| quicksort |  0.0827    | *0.0310    | *0.0709    | *0.0771    | *0.1412    |
|           | 19% slower | 30% faster | 25% faster | 31% faster | 40% faster |
+-----------+------------+------------+------------+------------+------------+

Original Notes from 2009

I tried a usort, and sorted 18 15000 Person objects in around 1.8 seconds.

As 17 you are concerned about the inefficiency 16 of the calls to the comparison function, I 15 compared it with a non-recursive Quicksort implementation. This 14 actually ran in around one third of the 13 time, approx 0.5 seconds.

Here's my code 12 which benchmarks the two approaches

// Non-recurive Quicksort for an array of Person objects
// adapted from http://www.algorithmist.com/index.php/Quicksort_non-recursive.php
function quickSort( &$array )
{
 $cur = 1;
 $stack[1]['l'] = 0;
 $stack[1]['r'] = count($array)-1;

 do
 {
  $l = $stack[$cur]['l'];
  $r = $stack[$cur]['r'];
  $cur--;

  do
  {
   $i = $l;
   $j = $r;
   $tmp = $array[(int)( ($l+$r)/2 )];

   // partion the array in two parts.
   // left from $tmp are with smaller values,
   // right from $tmp are with bigger ones
   do
   {
    while( $array[$i]->age < $tmp->age )
     $i++;

    while( $tmp->age < $array[$j]->age )
     $j--;

    // swap elements from the two sides
    if( $i <= $j)
    {
     $w = $array[$i];
     $array[$i] = $array[$j];
     $array[$j] = $w;

     $i++;
     $j--;
    }

   }while( $i <= $j );

 if( $i < $r )
   {
    $cur++;
    $stack[$cur]['l'] = $i;
    $stack[$cur]['r'] = $r;
   }
   $r = $j;

  }while( $l < $r );

 }while( $cur != 0 );


}


// usort() comparison function for Person objects
function personSort( $a, $b ) {
    return $a->age == $b->age ? 0 : ( $a->age > $b->age ) ? 1 : -1;
}


// simple person object    
class Person {
  var $age;
  function __construct($age) {
    $this->age = $age;
  }
}

//---------test internal usort() on 15000 Person objects------

srand(1);
$people=array();
for ($x=0; $x<15000; $x++)
{
     $people[]=new Person(rand(1,100));
}


$start=microtime(true);
usort( $people, 'personSort' );
$total=microtime(true)-$start;

echo "usort took $total\n";


//---------test custom quicksort on 15000 Person objects------

srand(1);
$people=array();
for ($x=0; $x<15000; $x++)
{
     $people[]=new Person(rand(1,100));
}


$start=microtime(true);
quickSort( $people );
$total=microtime(true)-$start;

echo "quickSort took $total\n";

An interesting 11 suggestion was to add a __toString method to the class 10 and use sort(), so I tried that out too. Trouble 9 is, you must pass SORT_STRING as the second 8 parameter to sort get it to actually call 7 the magic method, which has the side effect 6 of doing a string rather than numeric sort. To 5 counter this, you need to pad the numbers 4 with zeroes to make it sort properly. Net 3 result was that this was slower than both 2 usort and the custom quickSort

sort 10000 items took      1.76266698837
usort 10000 items took     1.08757710457
quickSort 10000 items took 0.320873022079

Here's the 1 code for the sort() using __toString():

$size=10000;

class Person {
  var $age;
  function __construct($age) {
    $this->age = $age;
    $this->sortable=sprintf("%03d", $age);
  }


  public function __toString()
  {
     return $this->sortable;
  }
}

srand(1);
$people=array();
for ($x=0; $x<$size; $x++)
{
     $people[]=new Person(rand(1,100));
}


$start=microtime(true);
sort( $people, SORT_STRING);
$total=microtime(true)-$start;

echo "sort($size) took $total\n"

For that specific scenario, you can sort 3 it using the usort() function, where you 2 define your own function to compare the 1 items in the array.

<?php

class Person {
  var $age;
  function __construct($age) {
    $this->age = $age;
  }
}

function personSort( $a, $b ) {
    return $a->age == $b->age ? 0 : ( $a->age > $b->age ) ? 1 : -1;
}

$person1 = new Person(14);
$person2 = new Person(5);
$person3 = new Person(32);
$person4 = new Person(150);
$person5 = new Person(39);
$people = array($person1, $person2, $person3, $person4, $person5);

print_r( $people );

usort( $people, 'personSort' );

print_r( $people );

You could either use usort or a heap.

 class SortPeopleByAge extends SplMaxHeap
  {
      function compare($person1, $person2)
      {
          return $person1->age - $person2->age;
      }
  }

  $people = array(new Person(30), new Person(22), new Person(40));  
  $sorter = new SortPeopleByAge;
  array_map(array($sorter, 'insert'), $people);
  print_r(iterator_to_array($sorter)); // people sorted from 40 to 22

Note that the 13 purpose of an Heap is to have an ordered 12 collection at all times and not to replace 11 usort. For large collections (1000+), a heap will be faster and less memory intensive though.

An added benefit of having Heaps is being 10 able to use their comparison function for 9 callbacks to other sorting functions, like 8 usort. You just have to remember that the order 7 for the comparison is reversed, so any comparison 6 done with a Heap will result in reversed 5 order in usort.

// using $people array and $sorter
usort($people, array($sorter, 'compare'));
print_r($people); // people sorted from 22 to 40

usort is fine for small to medium collections 4 where you will do the sorting once at the 3 end. Of course, you dont have to have a 2 heap to use usort. You can just as well add any 1 other valid callback for the sorting.

I just coded this. It should be faster than 3 usort as it does not rely on numerous function 2 calls.

function sortByProp($array, $propName, $reverse = false)
{
    $sorted = [];

    foreach ($array as $item)
    {
        $sorted[$item->$propName][] = $item;
    }

    if ($reverse) krsort($sorted); else ksort($sorted);
    $result = [];

    foreach ($sorted as $subArray) foreach ($subArray as $item)
    {
        $result[] = $item;
    }

    return $result;
}

Usage:

$sorted = sortByProp($people, 'age');

Oh, and it uses ksort but it works 1 even if many $people are of the same $age.

You just need to write a custom comparison 4 function, then use something like usort to do 3 the actual sorting. For example, if the 2 member variable was myVar, you could sort it 1 as follows:

function cmp($a, $b)
{
    if ($a->myVar == $b->myVar) {
        return 0;
    }
    return ($a->myVar < $b->myVar) ? -1 : 1;
}

usort($myArray, "cmp");

I do not advice my solution in your example 3 because it would be ugly (And I have not 2 benchmarked it), but it works.... And depending 1 of the need, it may help. :)

class Person
{
  public $age;

  function __construct($age)
  {
    $this->age = $age;
  }

  public function __toString()
  {
    return $this->age;
  }
}

$person1 = new Person(14);
$person2 = new Person(5);

$persons = array($person1, $person2);
asort($persons);

Here’s a stable Radix Sort implementation for values 0...256:

function radixsort(&$a)
{
    $n = count($a);
    $partition = array();
    for ($slot = 0; $slot < 256; ++$slot) {
        $partition[] = array();
    }
    for ($i = 0; $i < $n; ++$i) {
        $partition[$a[$i]->age & 0xFF][] = &$a[$i];
    } 
    $i = 0;
    for ($slot = 0; $slot < 256; ++$slot) {
        for ($j = 0, $n = count($partition[$slot]); $j < $n; ++$j) {
            $a[$i++] = &$partition[$slot][$j];
        }
    }
}

This 2 costs only O(n) since Radix Sort is a non-comparing 1 sorting algorithm.

One observation is that if the source of 4 the data is from a database, it's probably 3 faster to sort using SQL than it would be 2 within PHP. Of course this is moot if 1 the data source is from a CSV or XML file.

I went with the following approach: created 4 a function that takes an array of objects, then 3 inside the function I create an associative 2 array using the property as key for the 1 array, then sort they array keys using ksort:

class Person {
    var $age;
    function __construct($age) {
      $this->age = $age;
    }
}

function sortPerson($persons = Array()){
    foreach($persons as $person){
        $sorted[$person->age] = $person;
    }
    ksort($sorted);
    return array_values($sorted);
}

$person1 = new Person(14);
$person2 = new Person(5);

$persons = array($person1, $person2);
$person = sortPerson($persons);

echo $person[0]->age."\n".$person[1]->age;
/* Output:
5
14
*/

You can do it with ouzo goodies:

$result = Arrays::sort(array($person1, $person2), Comparator::compareBy('age'));

http://ouzo.readthedocs.org/en/latest/utils/comparators.html

0

usort() or uasort() /* to maintain index association if you were using an associative array */

0

Yes. If you implement spl ArrayObject in your person object, all 2 the normal php array functions will work 1 properly with it.

Try usort: http://www.php.net/manual/en/function.usort.php

Example:

<?php
function cmp($obja, $objb)
{
    $a = $obja->sortField;
    $b = $objb->sortField;
    if ($a == $b) {
        return 0;
    }
    return ($a < $b) ? -1 : 1;
}

$a = array( /* your objects */ );

usort($a, "cmp");

?>

0

If all member variables in question are 9 guaranteed to be different, it will be simpler 8 and faster to create a new collection indexed 7 by these values and then ksort it:

 foreach($obj_list as $obj)
    $map[$obj->some_var] = $obj;
 ksort($map);
 /// $map now contains the sorted list

If there are 6 duplicate values, you can still avoid usort by 5 utilizing a less known feature of sort that 4 arrays of arrays are sorted by the value 3 of the first scalar member.

 foreach($obj_list as $obj)
    $map[] = array($obj->some_var, $obj);
 sort($map); // sorts $map by the value of ->some_var

I guess this 2 still will be 10000000 times faster than 1 usort

Here is an option that takes following things 1 into account:

• namespaces
• private properties
• using getter and setter methods
• property for sort as parameter

PHP

namespace Dummy;

class Person {

    private $age;

    function __construct($age) {
        $this->setAge($age);
    }

    public function getAge()
    {
        return $this->age;
    }

    public function setAge($age)
    {
        $this->age = $age;
    }
}

class CustomSort{

    public $field = '';

    public function cmp($a, $b)
    {
        return strcmp($a->{'get'.ucfirst($this->field)}(), $b->{'get'.ucfirst($this->field)}());
    }

    public function sortObjectArrayByField($array, $field)
    {
        $this->field = $field;
        usort($array, array("Dummy\CustomSort", "cmp"));
        return $array;
    }
}

$robert = new Person(20);
$peter = new Person(12);
$robin = new Person(44);
$people = array($robert, $peter, $robin);

var_dump( $people );

$customSort = new CustomSort();
$people = $customSort->sortObjectArrayByField($people, 'age');

var_dump( $people );