Sort array by object property in PHP?

Question

If I have an object as such:

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

and I have any array of Person's

$person1 = new Person(14);
$person2 = new Person(5);
$people = array($person1, $person2);

Is there an easy way to sort the $people array by the Person->age property?

Answer 1

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

Answer 2

For that specific scenario, you can sort it using the usort() function, where you define your own function to compare the 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 );

Answer 3

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

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

Here's my code 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 suggestion was to add a __toString method to the class and use sort(), so I tried that out too. Trouble is, you must pass SORT_STRING as the second parameter to sort get it to actually call the magic method, which has the side effect of doing a string rather than numeric sort. To counter this, you need to pad the numbers with zeroes to make it sort properly. Net result was that this was slower than both 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 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"

Answer 4

I do not advice my solution in your example because it would be ugly (And I have not benchmarked it), but it works.... And depending 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);

Answer 5

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 costs only O(n) since Radix Sort is a non-comparing sorting algorithm.

Answer 6

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

Answer 7

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