Roll-my-own quicksort question

[saintp]

Okay, so I'm doing some serious jiggerpokery with OOP in PHP, and I've got to roll my own sort algorithm. (I'm sorting an array of objects by a property of one of the child objects.) So I went out and picked up some quicksort pseudocode:

QuickSort(A, p, r)
if p < r
then q = Partition(A,p,r)
Quicksort(A,p,q)
Quicksort(A,q+1,r) Notes:

initially call with
A = unsorted array
p = 1
r = size of (A)

Partition Pseudocode
Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while TRUE
do repeat j = j -1
until A[j] <= x
repeat i = i + 1
until A >= x
if i < j
then exchange A with A[j]
else return j

from http://astro.gmu.edu/classes/c80196/lecture3.html. This looks nothing like PHP, so here's what I did with it (roughly -- I don't want to bore and confuse you with the details of the OOP):

function quicksort($array, $p, $r) {
if ($p < $r) $q = partition($array, $p, $r)
quicksort($array, $p, $q)
quicksort($array, $q + 1, $r)
}

function partition($array, $p, $r) {
$x = $array[$p];
for ($j = $r + 1; $array[$j] <= $x; $j--) {
for ($i = $p - 1; $array[$i] >= $x; $i--) {
if ($i < $j) {
$temp = $array[$i];
$array[$i] = $array[$j];
$array[$j] = $temp;
} else return $j
}
}
}

Now, there might be little typos in there because, as I noted, that's not exactly what I have due to my nasty OOP.

I've never done my own quicksort before, and the pseudocode was a little unclear to me, so I'm not sure my algorithm is right. Actually, I'm pretty sure it isn't right. The only PHP-code quicksort I can find is totally undecipherable (a lesson in meaningful variable names: http://pulsar.jb.com/sklar-php/code5.html), so can anyone tell me if I'm on the right track here? Maybe some suggestions as to what's wrong? Thanks.

[tomhath]

It looks like you are pretty close. Make sure your partition function is acting on the original array and not a copy of it so you'll have a sorted array when you return from the function.

Quicksort is a very simple 4 step algorithm:

1) Look at the input array as two halves (I think of them as the left side and right side of the input array). You call this the $p and $r array indexes.

2) Move all the "low" values from the input array to the left side and all the "high" values to the right side (this is your partition function)

3) The left side now contains values that are less than anything in the right side, so quicksort this half of the array to order it (see steps 1 through 4)

4) And right side contains values greater than anything on the left side, so quicksort this half of the array to order it (see steps 1 through 4)

When it returns from all the recursion, the lowest values will have been moved all the way to the left and the highest will have been moved all the way to the right. Presto chango, the array is sorted.

The tricky part is deciding where to split the array, and what value is low vs. high at each step. Partition starts at each end of the half-array and works toward the other end until every value has been thrown to one end or the other.