Tri rapide avec un pivot aléatoire en Java

Question

J'ai été affecté à la mise en place d'un tri rapide avec un point de pivotement aléatoire (parce que c'est censé être le moyen le plus efficace/le plus sûr), mais j'ai été asservi à un bogosort. Quelqu'un peut-il me diriger sur la façon de le faire? Et quelqu'un peut-il m'aider à regarder mon bogosort pour voir si je peux le sauver quand même?

public static void Quick(int[] target, int lo, int hi) { 
    if(hi-lo==0){return;} 
    Random numberGenerator = new Random(); 
    int pivot = (numberGenerator.nextInt(hi-lo)+lo); 
    int high; 
    for(high=hi; high>pivot ; high--){ 
     if(target[high]<target[pivot]){ //if highest was smaller than pivot, move far end 
      if(high-pivot==1){ 
       int temp=target[high]; 
       target[high]=target[pivot]; 
       target[pivot]=temp; 
      } 
      else{ 
       int temp1 = target[pivot]; 
       int temp2 = target[pivot+1]; 
       target[pivot]=target[high]; 
       target[pivot+1]=temp1; 
       target[high]=temp2; 
      } 
     } 
    } 
    int low; 
    for(low=lo; low<pivot ; low++){ 
     if(target[low]>target[pivot]){ //if highest was smaller than pivot, move far end 
      if(pivot-low==1){ 
       int temp=target[low]; 
       target[low]=target[pivot]; 
       target[pivot]=temp; 
      } 
      else{ 
       int temp1 = target[pivot]; 
       int temp2 = target[pivot-1]; 
       target[pivot]=target[low]; 
       target[pivot-1]=temp1; 
       target[low]=temp2; 
      } 
     } 
    } 
    if(low-lo>0){ 
     Quick(target, lo, low-1); 
    } 
    if(hi-high>0){ 
     Quick(target, high+1, hi); 
    } 
} 

Answer 1

Voir cette pseudo-code pour inplace patitioning (de Wikipedia):

function partition(array, left, right, pivotIndex) 
    pivotValue := array[pivotIndex] 
    swap array[pivotIndex] and array[right] // Move pivot to end 
    storeIndex := left 
    for i from left to right - 1 // left ≤ i < right 
     if array[i] ≤ pivotValue 
      swap array[i] and array[storeIndex] 
      storeIndex := storeIndex + 1 
    swap array[storeIndex] and array[right] // Move pivot to its final place 
    return storeIndex 

Avis boucle sur la totalité du tableau (à l'exception du dernier indice). Le pivot n'est pas échangé jusqu'à la fin. Dans votre code, la valeur du pivot ne cesse de changer dans la boucle, ce qui ne semble pas correct.

Chaque fois qu'il y a un échange, la cible d'échange (storeIndex ci-dessus) doit changer.

De même, il vous suffit de permuter les valeurs inférieures au pivot situé à gauche. Si toutes les valeurs basses sont à gauche, alors les valeurs hautes finiront sur la droite.