Comment modifier le tri rapide en éléments de sortie dans l'ordre décroissant?

Question

J'ai écrit un algorithme de quicksort mais je voudrais faire un changement quelque part afin que ce quicksort produise des éléments dans l'ordre décroissant.

J'ai cherché et j'ai trouvé que je peux changer l'opérateur de comparaison (<) dans la partition() à l'inverse (comme ci-dessous).

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

Mais il ne fonctionne pas ..

Si je QuickSort le tableau ci-dessous, $ array = (3,9,5,7);

devrait être:

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

Mais la production réelle est:

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

Ci-dessous est mon quicksort qui essaie de sortir les éléments dans l'ordre décroissant. Comment effectuer un changement pour trier par ordre décroissant? Si vous avez besoin d'éclaircissements, faites-le moi savoir. Merci!

$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

permuter Juste les opérateurs de comparaison < avec > et vice versa lorsque l'on compare deux éléments:

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

Answer 2

Au lieu de changer la mise en œuvre de quicksort, itérer le tableau de la fin:

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