QuickSort OutOfBoundsエラー

Question

3つの値の中央値をピボットとして使用するquickSort関数を作成しようとしていますが、問題が発生しています。私は56,66,35,34、および84行目の範囲外のエラーに遭遇しており、これを無駄に変更しようとしています。何かご意見は？

public class MyQuickSort { 

    private int array[]; 
    private int length; 

    public void sort(int[] inputArr) { 

     if (inputArr.length == 0) { 
      return; 
     } 
     this.array = inputArr; 
     length = inputArr.length; 
     quickSort(0, length - 1); 
    } 

    private void quickSort(int lowerIndex, int higherIndex) { 

     int i = lowerIndex; 
     int j = higherIndex; 
     // calculate pivot number, I am taking pivot as middle index number 
     int mid = array[(higherIndex-1)/2]; 
     // Divide into two arrays 

     int pivot = findMedian(array, i, mid, j); 
     swap(pivot, 0); 

     while (i <= j) { 
      /** 
      * In each iteration, we will identify a number from left side which 
      * is greater then the pivot value, and also we will identify a number 
      * from right side which is less then the pivot value. Once the search 
      * is done, then we exchange both numbers. 
      */ 
      while (array[i] < mid) { 
       i++; 
      } 
      while (array[j] > mid) { 
       j--; 
      } 
      if (i <= j) { 
       swap(i, j); 
       //move index to next position on both sides 
       i++; 
       j--; 
      } 
     } 
     // call quickSort() method recursively 
     if (lowerIndex < j) 
      quickSort(lowerIndex, j); 
     if (i < higherIndex) 
      quickSort(i, higherIndex); 
    } 

    public static int findMedian (int[] array, int a, int b, int c) { 
     if ((array[a] > array[b] && array[a] < array[c]) || (array[a] > array[c] && array[a] < array[b])) { 
      return a; 
     } else if ((array[b] > array[a] && array[b] < array[c]) || (array[b] > array[c] && array[b] < array[a])) { 
      return b; 
     } 
     return c; 
    } 


    private void swap(int i, int j) { 
     int temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
    } 

    public static void main(String a[]){ 

     MyQuickSort sorter = new MyQuickSort(); 
     int[] input = {24,2,45,20,56,75,2,56,99,53,12}; 
     sorter.sort(input); 
     for(int i:input){ 
      System.out.print(i); 
      System.out.print(" "); 
     } 
    } 
} 

Answer 1

問題は、変数midがインデックスと値の両方として使用されていることです。 関数findMedian（）は、配列内の値ではなくインデックスのみを必要とします。

私はクイックソートを変更する場合は（）（これは、インデックスの境界midIndexをチェック含まれていることに注意してください）します

private void quickSort(int lowerIndex, int higherIndex) { 

     int i = lowerIndex; 
     int j = higherIndex; 
     // calculate pivot number, I am taking pivot as middle index number 
     int midIndex = (higherIndex-1)/2; 
     if (midIndex < lowerIndex) { 
      midIndex = lowerIndex; 
     } 
     int mid = array[midIndex]; 
     // Divide into two arrays 

     int pivot = findMedian(array, i, midIndex, j); 
     swap(pivot, i); 

     while (i <= j) { 
      /** 
      * In each iteration, we will identify a number from left side which 
      * is greater then the pivot value, and also we will identify a number 
      * from right side which is less then the pivot value. Once the search 
      * is done, then we exchange both numbers. 
      */ 
      while (array[i] < mid) { 
       i++; 
      } 
      while (array[j] > mid) { 
       j--; 
      } 
      if (i <= j) { 
       swap(i, j); 
       //move index to next position on both sides 
       i++; 
       j--; 
      } 
     } 
     // call quickSort() method recursively 
     if (lowerIndex < j) 
      quickSort(lowerIndex, j); 
     if (i < higherIndex) 
      quickSort(i, higherIndex); 
    } 

私が手：

java MyQuickSort 
2 2 12 20 24 45 53 56 56 75 99