MergeSort IllegalArgumentException

Question

これで、Project Eulerの問題を解決するMergeSortについて今すぐ学習しています。

アルファベット順にリスト5163の名前をソートしようとしています。私はいくつかの調査を行い、MergeSortがかなり効率的な方法であることを発見しました。

私はこのlinkに基づいて実装をコーディングしました。

以下は私のmergeSortおよびmergeの方法です。

Exception in thread "main" java.lang.IllegalArgumentException: fromIndex(1) > toIndex(0)

この行を指している：

List<String> rightSide = list.subList(list.size()/2 + 1, list.size()); 

public static List<String> mergeSort(List<String> list){ 

    if (list.size() == 1){ //if fully divided 
     return list; 
    } 

    List<String> leftSide = list.subList(0, list.size()/2); 
    List<String> rightSide = list.subList(list.size()/2 + 1, list.size()); 

    leftSide = mergeSort(leftSide); 
    rightSide = mergeSort(rightSide); 

    return merge(leftSide, rightSide); 

} 

public static List<String> merge(List<String> listA, List<String> listB){ 

    List<String> listC = new LinkedList<String>(); 

    while (!listA.isEmpty() & !listB.isEmpty()){ //while both have elements 
     if (listA.get(0).compareTo(listB.get(0)) > 1){ //if stringA is greater than stringB 
      listC.add(listA.get(0)); 
      listA.remove(0); 
     } else { //if stringB is greater than stringA 
      listC.add(listB.get(0)); 
      listB.remove(0); 
     } 
    } 

    while (!listA.isEmpty()){ //while listA has elements 
     listC.add(listA.get(0)); 
     listA.remove(0); 
    } 

    while (!listB.isEmpty()){ //while listB has elements 
     listC.add(listB.get(0)); 
     listB.remove(0); 
    } 

    return listC; 

} 

問題は、私がしようとすると名前の私のリストにmergeSortメソッドを使用する場合、それは私に次のエラーを与えることです

なぜそれが起こっているのか分かりません。チュートリアルに示されているのとまったく同じ方法を使っているようです。

また、わかりましたが、このエラーは私のリストのサイズがゼロであることを私に伝えています。これは、list.size()/2 + 1が1に等しく、list.size()が0に等しくなる唯一の方法です。しかし、私のリストがなぜゼロかもしれないのか分かりません。サイズが1になるまで分割されるので、それが返されます。

ゼロに等しいと見ることができる唯一の方法は、最初はゼロだったが、私がlist.size()が5163で始まることを確認した。

誰かが私が間違っていることを指摘するのに役立つでしょうか？私はそれが本当にシンプルなものだと確信していますが、私はこれを学び始めたばかりなので、それが何であるか分かりません。

EDIT：

私はここにリストのサイズをチェック：

System.out.println(namesArray.size()); //prints "5163" 
namesArray = mergeSort(namesArray); 

それでは、どのように私のリストは、これまでにゼロの大きさを持っているだろうか？

Answer 1

The only way I could see it equalling zero was if it was zero to begin with, but I have confirmed that my list.size() is 5163 to start with.

第2の方法があります。 mergeSortへの入力時に入力サブリストに2つの要素が含まれている場合、再帰の深刻な部分を考慮してください。

List<String> leftSide = list.subList(0, list.size()/2); 

上記はlist.sublist(0,1)になります。終了インデックスはで、であるため、サブリストには1つの要素が含まれています。次に：

List<String> rightSide = list.subList(list.size()/2 + 1, list.size()); 

これはlist.sublist(2,2)になります。再び、終了インデックスはの排他的であるので、の長さのリスト、またはのemtpyリストが作成されます。ここで、再帰呼び出しに達すると、

leftSide = mergeSort(leftSide); 
rightSide = mergeSort(rightSide); 

が返されますが、右側の再帰はゼロ長のリストを渡します。 mergeSortの一番上には、リストのサイズ1の終了条件をチェックしますが、空の長さゼロのリストを処理しようとするからコードを停止しません

if (list.size() == 1){ //if fully divided 
    return list; 
} 

を持っています。これがこのポイントの直後にあなたの例外を引き起こす原因です。

テストをif (list.size() <= 1)に変更した場合は、例外を防ぐことができましたが、終了インデックスの問題により一部の要素がソートされていないため、問題が残ることがあります。

正解が1行に変更することです：

List<String> rightSide = list.subList(list.size()/2 + 1, list.size()); 
                ^^^ 
     Remove this----------------------------------^ 

Answer 2

あなたは空のリストを持っている場合は、あなたが

List<String> rightSide = list.subList(0/2 + 1, 0); 

を呼び出すだからあなたの指標からは、toIndexのよりも大きいです。それは例外を発生させます。

フォームjavadoc：

Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive. (If fromIndex and toIndex are equal, the returned list is empty.) The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa. The returned list supports all of the optional list operations supported by this list. This method eliminates the need for explicit range operations (of the sort that commonly exist for arrays). Any operation that expects a list can be used as a range operation by passing a subList view instead of a whole list. For example, the following idiom removes a range of elements from a list: list.subList(from, to).clear();

Similar idioms may be constructed for indexOf and lastIndexOf, and all of the algorithms in the Collections class can be applied to a subList. The semantics of the list returned by this method become undefined if the backing list (i.e., this list) is structurally modified in any way other than via the returned list. (Structural modifications are those that change the size of this list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.)

Parameters:fromIndex - low endpoint (inclusive) of the subList

toIndex - high endpoint (exclusive) of the subListReturns:a view of the specified range within this list

Throws:IndexOutOfBoundsException - for an illegal endpoint index value (fromIndex < 0 || toIndex > size || fromIndex > toIndex)

あなたはリストが空であるかどうかを確認する必要があります。