クイックソートに失敗したこのテストはなぜですか？

Question

私は3つのアルゴの中央値を使ってクイックソートを実装しようとしていますが、小さなパーティションに関連して書いた単体テストには失敗します。私は私の以前のパーティションを変更し、今ではそれが失敗するのに使用テストのいずれかを渡しますが、まだ下に一つの失敗：

私のコードは次のとおりです。

public class QuickSort { 

    static void swap(int[] A, int i, int j) { 
     int tmp = A[i]; 
     A[i] = A[j]; 
     A[j] = tmp; 
    } 

static final int LIMIT = 15; 

static int partition(int[] a, int left, int right){ 
    int center = (left + right)/2; 
    if(a[center] < (a[left])) 
     swap(a,left,center); 
    if(a[right-1] < a[left]) 
     swap(a,left,right); 
    if(a[right-1] < a[center]) 
     swap(a,center,right); 

    swap(a,center,right - 1); 
    return a[right - 1]; 
} 


static void quicksort(int[] a, int left, int right){ 
    if(left + LIMIT <= right){ 
     int pivot = partition(a,left,right); 

     int i = left; 
     int j = right - 1; 

     for(;;){ 
      while(a[++i] < pivot){} 
      while(a[--j] > pivot){} 
      if(i < j) 
       swap(a,i,j); 
      else 
       break; 
     } 
     swap(a,i,right - 1); 
     quicksort(a,left,i-1); 
     quicksort(a,i+1,right); 
    } 
    else{ 
     insertionSort(a); 
    } 
} 

public static void insertionSort(int[] a){ 
    int j; 

    for(int p = 1; p < a.length; p++){ 
     int tmp = a[p]; 
     for(j = p; j > 0 && tmp < a[j-1]; j--) 
      a[j] = a[j-1]; 
     a[j] = tmp; 
    } 
} 

} 

このテストは失敗します。

public void smalltest() throws Exception { 
    int[] Arr_orig = {3,9,8,2,4,6,7,5}; 
    int[] Arr = Arr_orig.clone(); 
    int pivot = QuickSort.partition(Arr, 0, Arr.length); 
    for (int i = 0; i != pivot; ++i) 
     assertTrue(Arr[i] <= Arr[pivot]); //fails! 
    for (int i = pivot + 1; i != Arr.length; ++i) 
     assertTrue(Arr[pivot] < Arr[i]); 
} 

Answer 1

この順番で1右、右を使用しての間に矛盾があります：

if(a[right-1] < a[left]) 
     swap(a,left,right); 

あなたが決定する必要があり右が最後の要素のインデックスになる場合、または1 +インデックスが最後の要素（「終了」インデックス）になる場合。

他にも問題があるかもしれませんが、これが私が気づいた最初のものです。