Как изменить быструю сортировку для вывода элементов в порядке убывания?

Question

Я написал алгоритм быстрой сортировки, однако я хотел бы где-нибудь внести изменения, чтобы эта быстрая сортировка выводила элементы в порядке убывания.

Я искал и обнаружил, что могу изменить оператор сравнения (

 //This is snippet from partition() function    
        while($array[$l] < $pivot) { $l++; }
        while($array[$r] > $pivot) { $r--; }

Но это не работает ..

Если я быстро сортирую массив ниже, $ array = (3,9,5,7);

должно быть:

$ array = (9,7,5,3)

Но фактический результат:

$ массив = (3,5,7,9)

Ниже приведена моя быстрая сортировка, которая пытается выводить элементы в порядке убывания. Как мне внести изменения для сортировки в порядке убывания? Если вам нужны какие-либо разъяснения, пожалуйста, дайте мне знать. Спасибо!

$array = array(3,9,5,7);
$app = new QuicksortDescending();
$app->quicksortDesc($array, 0, count($array));
print_r($array);


class QuicksortDescending {

public function partitionDesc(&$array, $left, $right) {
        $l = $left;
        $r = $right;
        $pivot = $array[($right+$left)/2];

        while($l <= $r) {
            while($array[$l] > $pivot) { $l++; }
            while($array[$r] < $pivot) { $r--; }
            if($l <= $r) {// if L and R haven't cross
                $this->swap($array, $l, $r);
                $l ++;
                $j --;
            }
        }
        return $l;
    }


public function quicksortDesc(&$array, $left, $right) {
        $index = $this->partitionDesc($array, $left, $right);
        if($left < $index-1) { //if there is more than 1 element to sort on right subarray
            $this->quicksortDesc($array, $left, $index-1);
        }
        if($index < $right) { //if there is more than 1 element to sort on right subarray
            $this->quicksortDesc($array, $index, $right);
        }
    }

public function swap(&$array, $index1, $index2) {
        $tmp = $array[$index1];
        $array[$index1] = $array[$index2];
        $array[$index2] = $tmp;

    }

}

Answer 1

Просто поменяйте местами операторы сравнения < с > и наоборот при сравнении двух элементов:

while($array[$l] < $pivot) { $l++; }
while($array[$r] > $pivot) { $r--; }

Answer 2

Вместо изменения реализации быстрой сортировки итерируйте массив с конца:

for ($i = count($array)-1; $i>=0; $i--) {
  // do something with $array[$i];
}