-1

私はJavaが初めてで、マージソートを使用する必要がある場所で割り当てを行っていますが、引き続きエラーが発生します。ArrayList を使用しているため、多くの間違いを犯しています。以下のコードと、引き続き発生するエラーを投稿しました。なぜこれが起こっているのかを理解してくれる人はいますか?

import java.util.ArrayList;
import java.util.UUID;

public class mSort {

public static ArrayList<String> randomList() {
    ArrayList<String> a = new ArrayList<String>();

    for(int i = 0; i < 10; i++) {
        a.add(i, UUID.randomUUID().toString());
    }

    return a;
}

public void sort(ArrayList<String> list) {
    sortArray(0, list.size(), list);
}

private void sortArray(int low, int high, ArrayList<String> list) {
    if ((high - low) >= 1) {
        int middle1 = ( low + high ) / 2;
        int middle2 = middle1 + 1;

        sortArray(low, middle1, list);
        sortArray(middle2, high, list);
        merge(low, middle1, middle2, high, list);
    }
}

private void merge(int left, int middle1, int middle2, int right, ArrayList<String> list) {
    int leftIndex = left;
    int rightIndex = middle2;
    int combinedIndex = left;
    ArrayList<String> combined = new ArrayList<String>();
    ArrayList<String> data = list;

    while (leftIndex <= middle1 && rightIndex <= right) {
        if (data.get(leftIndex).compareTo(data.get(rightIndex)) < 0) {
            combined.add(combinedIndex, data.get(leftIndex));
            combinedIndex++;
            leftIndex++;
        }
        else {
            combined.add(combinedIndex, data.get(rightIndex));
            combinedIndex++;
            rightIndex++;
        }
    }

   if (leftIndex == middle2) {
       while (rightIndex <= right) {
           combined.add(combinedIndex, data.get(rightIndex));
           combinedIndex++;
           rightIndex++;
       }
   }
   else {
       while ( leftIndex <= middle1 ) {
           combined.add(combinedIndex, data.get(leftIndex));
           combinedIndex++;
           leftIndex++;
       }
   }
   for (int i = left; i <= right; i++ ) {
       list.set(i, combined.get(i));
       //System.out.println(list.get(i));
   }
}

public static void main(String[] args) {
    ArrayList<String> list = randomList();
    mSort sorted = new mSort();
    sorted.sort(list);

    for ( int i = 0; i < list.size(); i++ ) {
        System.out.println(list.get(i));
    }
}

}

エラーのスタック トレースは次のとおりです。

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 3, Size: 0
at java.util.ArrayList.rangeCheckForAdd(Unknown Source)
at java.util.ArrayList.add(Unknown Source)
at mSort.merge(mSort.java:40)
at mSort.sortArray(mSort.java:27)
at mSort.sortArray(mSort.java:25)
at mSort.sortArray(mSort.java:26)
at mSort.sortArray(mSort.java:25)
at mSort.sort(mSort.java:17)
at mSort.main(mSort.java:74)
4

2 に答える 2

1

いくつかの問題があります。

  1. sortArray(0, list.size(), list);sortArray(0, list.size() - 1, list);インデックスが 0 からサイズ - 1になるため、そうする必要があります。

  2. combined.add(combinedIndex, data.get(rightIndex));合流中の線。
    この範囲外のインデックスには追加できません0 <= index <= size。これを行うと、ドキュメントに従って IndexOutOfBoundsException をスローする必要があります。（それはそうです）。これが、例外が表示される理由です。結合された ArrayList のサイズは 0 であり、インデックス 3 に挿入しようとしています。
    これらの行をすべて変更して、そのままにすることができますcombined.add(data.get(...));(combinedIndex を削除します)。配列は既に部分的にソートされている必要があるため、結合されたインデックス変数は必要ありません。

  3. 結合された配列リストの size() の外に出ないように、merge alls の最後にある以下のブロックを変更する必要があります。下に示された。

前

for (int i = left; i <= right; i++ ) {
    list.set(i, combined.get(i));
}

後

for (int i = left; i <= right; i++ ) {
    list.set(i, combined.get(i - left));
}
于 2013-05-09T02:38:35.417 に答える
1

あなたが持っている配列インデックスが配列のサイズから1を引いたものよりも大きいために起こっています。配列インデックスは 0 から始まり、n-1 まで

于 2013-05-09T02:20:41.160 に答える