Merge Sort for Javaの実装に問題があります

Question

public static void main(String[] args) { 
    int[] test = {5,4,3,5,7,5,1,5,96}; 
    System.out.print("Before: "); 
    printList(test); 
    mergeSort(test, 1, test.length); 
    //System.out.print("After: "); 
    //printList(test); 
} 

public static void printList(int[] test){ 
    for (int i= 0; i < test.length; i++){ 
     System.out.print(test[i] + " "); 
    } 
    System.out.println(); 
} 

public static void merge(int[] A, int p, int q, int r){ 
    int n1 = q - p + 1; 
    int n2 = r - q; 

    int[] L = new int[n1]; 
    int[] R = new int[n2]; 

    for(int i = 1; i <= n1; i++){ 
     L[i] = A[p+i-1]; 
    } 
    for (int j = 1; j <= n2; j++){ 
     R[j] = A[q+j]; 
    } 
    int i = 1; 
    int j = 1; 

    for (int k=p; i <= r; i++){ 
     if (i > n1){ 
      A[k] = R[j]; 
      j++; 
     } 
     else if (j > n2){ 
      A[k] = L[i]; 
      i++; 
     } 
     else if (L[i] <= R[j]){ 
      A[k] = L[i]; 
      i++; 
     } 
     else{ 
      A[k] = R[j]; 
      j++; 
     } 
    } 
} 

public static void mergeSort(int[] A, int p, int r){ 
    if (p < r){ 
     int q = (p + r)/2; 
     mergeSort(A, p, q); 
     mergeSort(A, q+1, r); 
     merge(A, p, q, r); 
    } 
} 

私はテスト配列にマージソートを実装しようとしていますが、なぜこれでArrayIndexOutOfBoundsExceptionエラーが発生するのかわかりません。割り当ては、マージソートコードを変更して、検索時にセンチネルを使用しないようにすることです。

Before: 5 4 3 5 7 5 1 5 96 
    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1 
    at Lab1_2.merge(Lab1_2.java:28) 
    at Lab1_2.mergeSort(Lab1_2.java:61) 
    at Lab1_2.mergeSort(Lab1_2.java:59) 
    at Lab1_2.mergeSort(Lab1_2.java:59) 
    at Lab1_2.mergeSort(Lab1_2.java:59) 
    at Lab1_2.main(Lab1_2.java:8) 

これはエラーメッセージです。

Answer 1

あなたは、配列の境界（限界値）のうち、アレイにアクセスしようとしているので、あなたがArrayIndexOutOfBoundsExceptionがランタイム例外を取得しています。 マージ方法で

int[] L = new int[n1]; 

ようなあなたの文では、あなたは0からn1にインデックスにある要素を取得することができN1サイズの配列を宣言。 ただし、インデックスn1に要素を格納しようとしています。これは可能ではありません。なぜなら、0からsize-1までの要素を持つarray（ここではsizeは配列の長さです）がこれが理由の1つです。あなたは他の場所を発行しています。 私はあなたのコードを編集し、あなたのためにコードの仕事を願っています。

/* package whatever; // don't place package name! */ 

import java.util.*; 

import java.lang.*; 

import java.io.*; 


class Ideone 
    { 
    public static void main (String[] args) throws java.lang.Exception 
    { 
    // your code goes here 
     int[] test = {5,4,3,5,7,5,1,5,96}; 
    System.out.print("Before: "); 
    printList(test); 
    mergeSort(test, 0, test.length-1); 
    System.out.print("After: "); 
    printList(test); 
} 

public static void printList(int[] test){ 
for (int i= 0; i < test.length; i++){ 
    System.out.print(test[i] + " "); 
} 
System.out.println(); 
} 

public static void merge(int[] A, int p, int q, int r){ 
int n1 = q - p + 1; 
int n2 = r - q; 

int[] L = new int[n1]; 
int[] R = new int[n2]; 

for(int i = 0; i < n1; i++){ 
    L[i] = A[p+i]; 
} 
for (int j = 0; j < n2; j++){ 
    R[j] = A[q+j+1]; 
} 
//int i = 0; 
//int j = 0; 

    /* for (int k=p; i <= r; i++){ 
    if (i > n1){ 
     A[k] = R[j]; 
     j++; 
    } 
    else if (j > n2){ 
     A[k] = L[i]; 
     i++; 
    } 
    else if (L[i] <= R[j]){ 
     A[k] = L[i]; 
     i++; 
    } 
    else{ 
     A[k] = R[j]; 
     j++; 
    } 
    }*/ 

     int i = 0, j = 0; 


    int k = p; 
    while (i < n1 && j < n2) 
    { 
     if (L[i] <= R[j]) 
     { 
      A[k] = L[i]; 
      i++; 
     } 
     else 
     { 
      A[k] = R[j]; 
      j++; 
     } 
     k++; 
    } 


    while (i < n1) 
    { 
     A[k] = L[i]; 
     i++; 
     k++; 
    } 


    while (j < n2) 
    { 
     A[k] = R[j]; 
     j++; 
     k++; 
    } 

} 

public static void mergeSort(int[] A, int p, int r){ 
if (p < r){ 
    int q = (p + r)/2; 
    mergeSort(A, p, q); 
    mergeSort(A, q+1, r); 
    merge(A, p, q, r); 
} 
} 

} 

Answer 2

その配列インデックスに注意し、メイン

mergeSort(test,0, test.length-1); // change array init index 0 

に変更

Answer 3

良く読みやすいソリューションを使用すると、エラーが出るん何行目で

public class MergeSort { 

    private int[] array; 
    private int[] tempMergArr; 
    private int length; 

    public static void main(String a[]){ 

     int[] inputArr = {5,4,3,5,7,5,1,5,96}; 
     System.out.print("Before: "); 
     printList(inputArr); 
     MergeSort mms = new MergeSort(); 
     mms.sort(inputArr); 
     System.out.print("After: "); 
     printList(inputArr); 
    } 

    public static void printList(int[] test){ 
     for (int i= 0; i < test.length; i++){ 
      System.out.print(test[i] + " "); 
     } 
     System.out.println(); 
    } 
    public void sort(int inputArr[]) { 
     this.array = inputArr; 
     this.length = inputArr.length; 
     this.tempMergArr = new int[length]; 
     mergeSort(0, length - 1); 
    } 

    private void mergeSort(int lowerIndex, int higherIndex) { 

     if (lowerIndex < higherIndex) { 
      int middle = lowerIndex + (higherIndex - lowerIndex)/2; 
      // Below step sorts the left side of the array 
      mergeSort(lowerIndex, middle); 
      // Below step sorts the right side of the array 
      mergeSort(middle + 1, higherIndex); 
      // Now merge both sides 
      merge(lowerIndex, middle, higherIndex); 
     } 
    } 

    private void merge(int lowerIndex, int middle, int higherIndex) { 

     for (int i = lowerIndex; i <= higherIndex; i++) { 
      tempMergArr[i] = array[i]; 
     } 
     int i = lowerIndex; 
     int j = middle + 1; 
     int k = lowerIndex; 
     while (i <= middle && j <= higherIndex) { 
      if (tempMergArr[i] <= tempMergArr[j]) { 
       array[k] = tempMergArr[i]; 
       i++; 
      } else { 
       array[k] = tempMergArr[j]; 
       j++; 
      } 
      k++; 
     } 
     while (i <= middle) { 
      array[k] = tempMergArr[i]; 
      k++; 
      i++; 
     } 

    } 
}