Quicksort не сортировка

Question

Так что я пытаюсь создать метод quicksort, однако он не сортируется правильно. Heres мой вход и выход
в исходном массиве:
80,0 10,0 50,0 70,0 60,0 90,0 20,0 30,0 40,0 0,0
отсортированного массива:
0,0 30,0 20,0 80,0 40,0 60,0 70,0 10,0 90,0 50,0

Я попытался изменить цикл для for(int i = left; i < right; i++)
но теперь выход:
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

Это то, что вы хотите сделать:

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; 
} 

Я сделал код более понятным, имея хелпер swap метод. У вас было 3 ошибки в исходном коде:

• Ошибка одноразовую на границе контура
• Вы используете неправильный индекс, чтобы получить опорный элемент в цикле
• Вы поменялись местами элементы на неправильные показатели после цикла

Answer 2

изменения

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

в

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