How to quicksort over multiple columns

Question

I'm looking to quicksort some objects in php.

i'm sorting an array of OBJECTS

$object->x;
$object->y;
$object->z;

I want to first sort by x, then y, then z.

This is my quicksort function Where it accepts an array of jobjects, and sorts by a particular sortkey (x, y, or z column) The function returns a sorted array of objects, that have been sorted by the sortkey.

private function quicksort($objects, $sortKey) {
    if(count($objects) < 2) return $objects;

    $left = $right = array();

    reset($objects);
    $pivot_key = key($objects);
    $pivot = array_shift($objects);

    foreach($objects as $k => $v) {
        if($v->$sortKey < $pivot->$sortKey)
            $left[$k] = $v;
        else
            $right[$k] = $v;
    }

    return array_merge($this->quicksort($left,$sortKey), array($pivot_key => $pivot), $this->quicksort($right,$sortKey));
}

I can easily quicksort any individual column using a quicksort recursive algorithm, but grouping them together and then sorting those subgroups to the nth time is really messing with my head.

Is there an algorithm that I could be looking at?

Answer 1

You need a different approach than your initial thought. Instead of sorting recursively, do only one sort that takes all your criteria into mind at once, in a ranked fashion (i.e. if x is same, test for y, and so on).

Others have already pointed to sorting functions that take a such called comparison function as an argument. The comparison function is given two of your objects and returns which object is smaller/greater than the other.

In the code you posted, you have this comparison:

    if($v->$sortKey < $pivot->$sortKey)

Instead of the test $v->$sortKey < $pivot->$sortKey, you need a call to your own comparison function, e.g.

    if (smaller($v, $pivot))

In the function smaller(), you define your rules.

private function smaller($obj1, $obj2) {
    if ($obj1->x < $obj2->x)
        return true;
    if ($obj1->x > $obj2->x)
        return false;
    if ($obj1->y < $obj2->y)
        return true;
    if ($obj1->y > $obj2->y)
        return false;
}

... and so on. As you can see, the sorting will ensure ordering according to x, and in the case that x is same (not smaller, not greater) continue to order according to y.

Answer 2

Are you implementing your own sort? Have you checked out http://us3.php.net/usort?

usort() can accept a comparison function, so you can implement pretty much any ordering rules you want.