Sort an array of objects by one of the objects property with PHP

Quicksort algorithm animationIf you want to sort an array of objects but using one of its object properties you can do it with usort, but this could take a lot of time and will be very computational expensive.
So I have implemented one method you can insert into one of your PHP classes. This method implements the quicksort algorithm.

As a result I have experienced a huge performance improvement against usort: one array of objects with 10.000 elements sorted with usort takes ~3.4 sg, and with quicksort algorithm takes, in my samples, ~0.56 sg. Awesome isn’t it?

Just take the code:

/**
* Sort one array of objects by one of the object's property
*
* @param mixed $array, the array of objects
* @param mixed $property, the property to sort with
* @return mixed, the sorted $array
*/
static public function sortArrayofObjectByProperty( $array, $property )
{
    $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 )];

            // split the array in to parts
            // first: objects with "smaller" property $property
            // second: objects with "bigger" property $property
            do
            {
                while( $array[$i]->{$property} < $tmp->{$property} ) $i++;
                while( $tmp->{$property} < $array[$j]->{$property} ) $j--;

                // Swap elements of two parts if necesary
                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 );

    return $array;

}

  • Richard

    This works perfectly. It was exactly what I was looking for. Thank you for sharing this great piece of code.

  • R

    oh hell yes…just what I needed..thanks so much!

  • Mahmudur Rahman

    It would great, if it has another parameter for ordering.

  • Pingback: Sort an array of objects by one of the properties in PHP | Crafty Coding()

  • Djembefola

    Damn that animation had me staring for far too long ;)

  • Sebastian Mordziol

    How well this algorithm performs depends on the type of data sorted, how well sorted it already is, and the size of the data set. In a current project, I had over a hundred calls to my sorting function, which had to sort an array of objects containing over 2000 objects.

    I was using usort to sort the objects array, but profiling showed that it was creating a lot of overhead. After searching a while for alternatives, I tried the quicksort algorithm and also tested your method. In my case, quicksort was about as slow as usort.

    In the end, what proved to be the fastest was to create a hash array first, like so:

    $sort = array();foreach($this->items as $item) { $sort[$item->property] = $item;
    }
    ksort($sort, SORT_NUMERIC);$this->items = array_values($sort);

    Obviously, you have to set the right ksort flag foir the data type you are comparing. This is a lot more verbose, but ksort has a much simpler job in this case sorting the keys than usort has, using the same data.

    Again, your mileage varies – you have to find the adequate solution for each use case.

  • keron

    This works like a charm! Thank you. Now to study it!

  • Matt Chandler

    Thank you Sebastian! This helped me a ton.

  • Pingback: Sort an array of objects by one of the properties in PHP | Lisa-Marie Karvonen()

  • Pepe López

    I needed both “DESC” and “ASC” sort, so i did a little change:

    I’ve just added a new param:

    public function sortArrayofObjectByProperty($array, $property, $asc = true)

    and changed lines 33 and 34 for:

    if ($desc) {
    while( $array[$i]->{$property} {$property} ) $i++;
    while( $tmp->{$property} {$property} ) $j–;
    } else {
    while( $array[$i]->{$property} > $tmp->{$property} ) $i++;
    while( $tmp->{$property} > $array[$j]->{$property} ) $j–;
    }

    Is that what you mean?

  • ans maria thomas

    Thanks .This works fine.