MergeSortアルゴリズム - java

Question

JavaでMergeSort実装に問題があります。私のコードはこのように見え、私はどこでミスをしたのか分かりません。

public List sort(List list) { 
     return mergesort(list, 0, list.size() - 1); 
    } 

    private List mergesort(List list, int startIndex, int endIndex) { 
     if (startIndex == endIndex) { 
      List temp = new ArrayList(); 
      temp.add(list.get(0)); 
      return temp; 
     } 
     int splitIndex = ((startIndex + endIndex)/2); 
     List list1 = mergesort(list, startIndex, splitIndex); 
     List list2 = mergesort(list, (splitIndex + 1), endIndex); 
     return merge(list1, list2); 
    } 

    private List merge(List left, List right) { 
     List result = new ArrayList(); 
     ListIterator l = new ListIterator(left); 
     ListIterator r = new ListIterator(right); 
     l.first(); 
     r.first(); 
     while (!l.isDone() && !r.isDone()) { 
      if (comparator.compare(l.current(), r.current()) <= 0) { 
       result.add(l.current()); 
       l.next(); 
      } else { 
       result.add(r.current()); 
       r.next(); 
      } 
     } 
     while (!l.isDone()) { 
      result.add(l.current()); 
      l.next(); 
     } 
     while (!r.isDone()) { 
      result.add(r.current()); 
      r.next(); 
     } 
     return result; 

    } 

私のアルゴリズムをテストするために、私は人のリストを使用し、年齢によって昇順にそれらを並べ替える：

0. Jan, Kowalski, 60 
1. Jerzy, Adamczewski, 59 
2. Jan, Kowalski, 48 
3. Adam, Malysz, 40 
4. Bartosz, Tusk, 50 
5. Zygmunt, Jacewicz, 41 

、出力は次のようになります。

0. Adam, Malysz, 40 
1. Adam, Malysz, 40 
2. Adam, Malysz, 40 
3. Adam, Malysz, 40 
4. Adam, Malysz, 40 
5. Adam, Malysz, 40 

Answer 1

このブロックには見えません右。

if (startIndex == endIndex) { 
    List temp = new ArrayList(); 
    temp.add(list.get(0)); 
    return temp; 
} 

おそらく、あなたはtemp.add(list.get(startIndex));を意味しましたか？

Answer 2

マージ関数は、リストが空になるまで常に同じ最小の要素を取るようです。これは、 "ListIterator :: current（）"と "ListIterator :: next（）"の使用に関する問題があるという印象を与えてくれます。

私はListIteratorsにあまり堪能ではありませんので、私の提案はリストに対して直接操作することです。

private List merge(List left, List right) { 
    List result = new LinkedList(); 

    while (!left.isEmpty() && !right.isEmpty()) { 
     if (comparator.compare(left.get(0), right.get(0)) <= 0) { 
      result.add(left.remove(0)); 
     } else { 
      result.add(right.remove(0)); 
     } 
    } 

    // add what is left in the lists 
    result.addAll(left); 
    result.addAll(right); 

    return result; 
} 

PS：私は私のIDEにこのコードを確認するため、注意して使用していなかったこれもその一つは、要素を使い果たした後、二つのリストの残りの要素を追加することが簡素化されます。 TDDはすべてのソフトウェア開発者が従うべき本当に良いアプローチです。