MergeSort-Algorithmus - Java

Question

Ich habe ein Problem mit der MergeSort-Implementierung in Java. Mein Code sieht so aus und ich habe keine Ahnung, wo ich einen Fehler gemacht habe.

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; 

    } 

mein Algorithmus Um zu testen, verwendete ich Liste von Personen und sortieren sie nach Alter aufsteigend:

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

Und die Ausgabe sieht wie folgt aus:

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

Dieser Block sieht nicht Recht.

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

Vielleicht meinen Sie temp.add(list.get(startIndex));?

Answer 2

Es scheint, dass Sie Funktion zusammenführen immer die gleichen kleinsten Elemente dauert, bis die Listen leer sind. Dies gibt mir den Eindruck, dass es ein Problem bei der Verwendung von "ListIterator :: current()" und "ListIterator :: next()" gibt.

Ich bin nicht sehr kompetent mit ListIterators, also ist mein Vorschlag, direkt auf den Listen zu operieren. Dies vereinfacht das Hinzufügen auch die übrigen Elemente der beiden Listen nach einem von ihnen läuft aus Elementen:

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: Ich habe diesen Code in meinem IDE nicht überprüfen, so verwenden Sie vorsichtig. Idealerweise sollten Sie Tests haben, die Ihren Code überprüfen - TDD ist ein wirklich guter Ansatz, dem jeder Softwareentwickler folgen sollte: