Quicksort pas de tri

Question

J'essaie donc de créer une méthode quicksort, mais elle ne fonctionne pas correctement. Heres mon entrée et de sortie
tableau original:
80,0 10,0 50,0 70,0 60,0 90,0 20,0 30,0 40,0 0,0
tableau trié:
0,0 30,0 20,0 80,0 40,0 60,0 70,0 10,0 90,0 50,0

J'ai essayé de changer la boucle à for(int i = left; i < right; i++)
mais maintenant la sortie est:
0,0 20,0 30,0 40,0 80,0 10,0 60,0 90,0 70,0 50,0

public static void sort(double[] a) 
    { 
     quickSort(a, 0, a.length-1); 
    } 

    public static void quickSort(double [] a, int left, int right) 
    { 
     if (left < right) 
     { 
      int pivotIndex = (left+right)/2; 
      int pos = partition(a,left,right,pivotIndex); 
      quickSort(a,left,pos-1); 
      quickSort(a,pos+1,right); 
     } 
    } 

    private static int partition(double [] a, int left,int right,int pivotIndex) 
    { 
     double temp = a[pivotIndex]; 
     a[pivotIndex] = a[right]; 
     a[right] = temp; 
     int pos = left;//represents boundary between small and large elements 
     for(int i = left; i < right-1; i++) 
     { 
      if (a[i] <= a[pivotIndex]) 
      { 
       double temp2 = a[i]; 
       a[i] = a[pos]; 
       a[pos] = temp2; 
       pos++; 
      } 
     } 
     double temp3 = a[pivotIndex]; 
     a[pivotIndex] = a[pos]; 
     a[pos] = temp3; 
     return pos; 
    } 

Answer 1

Voici ce que vous voulez faire:

private static void swap(double[] a, int i, int j) { 
    double t = a[i]; 
    a[i] = a[j]; 
    a[j] = t; 
} 

private static int partition(double [] a, int left,int right,int pivotIndex) 
{ 
    swap(a, pivotIndex, right); 
    int pos = left;//represents boundary between small and large elements 
    for(int i = left; i < right; i++) 
    { 
     if (a[i] < a[right]) 
     { 
      swap(a, i, pos); 
      pos++; 
     } 
    } 
    swap(a, right, pos); 
    return pos; 
} 

J'ai fait le code plus clair en ayant une méthode aide swap. Vous avez eu 3 bugs dans le code d'origine:

• L'erreur unique sur la limite de la boucle
• Vous utilisez le mauvais index pour obtenir l'élément pivot dans la boucle
• Vous permuté éléments à la mauvais indices après la boucle

Answer 2

changement

for(int i = left; i < right-1; i++) 

à

for(int i = left; i < right; i++)