How do you sort an array of objects?

ppowell

The PHP Manual offered me NO help on this one, so now I appeal to the populace:

$dirID = @opendir('/my/path/to/files');
while (($fyl = @readdir($dirID)))  {
  $obj =& new ClassObject($fyl);
   array_push($imageArray, $obj);
   $obj = null;
}

I now have an array $imageArray of objects as so:

$imageArray[0]->image_name

$imageArray[0]->image_dimensions

I need to sort $imageArray by "image_name" or by "image_dimensions" and I can't think of a way to do it, any ideas?

Thanx
Phil

bubblenut

Think you're going to have to build you're own sorting function I'm afraid.
There are many sorting algorithms (a few are listed in the link below) but in order to choose between them you really need to know the nature of your data. I would suggest using a selection, insertion or quick sort. Avoid the bubble sort, although it's easy to implement and similar to my name, which are both very attractive qualities, it is notoriously slow (general case O(n²⁾ and inifeciently done to boot).
Sorting Explinations
HTH
Bubble

ppowell

I'm aware of all of the sorting options in PHP but all of them address it from the standpoint that an array is a collection of variables keyed by an integer or a string.

There is nothing about a collection of OBJECTS keyed together by an integer or a string (knowing that keys can only be integers and/or strings).

sigh I was hoping there'd be something out there, writing my own is customizable but time-consuming.

Thanx
Phil

bubblenut

I haven't tested this at all yet and I'm about to go home yet so you won't hear for a couple of days if I do.
It's basically a reworking of the quicksort example given in the link provided in my last post but allows you to select what the array is made up of (array or object) and what variable you wish to use to sort on. Have a play with it and strip out what you don't need. Quicksort is a recursive search so the code in q_search() will get executed a lot of times (don't really want that case statement in there if we can avoid it, just use the object option for your code and strip out the rest)

<?php
<?php
function quicksort(&$array,$arrayof,$fieldname)
{
    $array_count=count($array);
    q_sort(&$array,0,$array_count-1,$arrayof,$fieldname);
}

function q_sort(&$array,$left, $right, $arrayof, $fieldname)
{
    $l_hold=$left;
    $r_hold=$right;
    switch($arrayof) {
        case 'object':
            $pivot=$array[$left]->{$fieldname};
            while($left<$right) {
                while($array[$right]->{$fieldname}>=$pivot && $left<$right)
                    $right--;
                if($left!=$right) {
                    $array[$left]=$array[$right];
                    $left++;
                }
                while($array[$left]->{$fieldname}<=$pivot && $left<$right)
                    $left++;
                if($left!=$right) {
                    $array[$right]=$array[$left];
                    $right--;
                }
            }
            break;
        case 'array':
            $pivot=$array[$left][$fieldname];
            while($left<$right) {
                while($array[$right][$fieldname]>=$pivot && $left<$right)
                    $right--;
                if($left!=$right) {
                    $array[$left]=$array[$right];
                    $left++;
                }
                while($array[$left][$fieldname]<=$pivot && $left<$right)
                    $left++;
                if($left!=$right) {
                    $array[$right]=$array[$left];
                    $right--;
                }
            }
            break;
        default:
            $pivot=$array[$left];
            while($left<$right) {
                while($array[$right]>=$pivot && $left<$right)
                    $right--;
                if($left!=$right) {
                    $array[$left]=$array[$right];
                    $left++;
                }
                while($array[$left][$fieldname]<=$pivot && $left<$right)
                    $left++;
                if($left!=$right) {
                    $array[$right]=$array[$left];
                    $right--;
                }
            break;
    }
    $array[$left]=$pivot;
    $pivot=$left;
    $left=$l_hold;
    $right=$r_hold;
    if($left<$pivot)
        q_sort($array,$left,$pivot-1,$arrayof,$fieldname);
    else
        q_sort($array,$pivot+1,$right,$arrayof,$fieldname);
}
?>

HTH
Bubble

ppowell

I've seen this notation before:

O(n²⁾

I have no idea what it means, can someone elaborate, please?

Thanx
Phil

swr

Use [man]usort[/man]! Then you only need to define a comparison function, instead of having to re-implement the whole search funtion.

Big-O notation refers to the complexity of the algorithm. Bubblesort, being O(n^2), would require on the order of 10,000 operations to sort a list of 100 items, or 1,000,000 operations to sort a list of 1000 items. This is bad, because the complexity goes up really fast as you increase the size of the data. Note that this isn't how fast it is, or exactly how many operations it takes, but it gives a general description of how the algorithm scales.

"Real" sort algorithms (quicksort, heapsort, mergesort, maybe others) run in O(n*(log(n))) time. Those algorithms would only require on the order of 10,000 operations to sort 1000 items.

If you really want to learn a good sort algorithm, I find mergesort is easier than quicksort (don't need to choose a pivot algorithm, fewer opportunities for off-by-one errors, etc). It's not as fast as quicksort but it is still way faster than bubblesort (except on tiny amounts of data, in which case you don't really care how fast it is anyway). It is also "stable", meaning it doesn't change the order of items that compare equal (unlike quicksort and heapsort).