Etwas löscht 3 Elemente aus meiner ArrayList

Question

Als Teil der Hausaufgaben müssen wir eine Merge-Sort implementieren. Keine große Sache, ich habe es schon einmal gemacht. Dieses Mal, obwohl ich eine IndexOutOfBoundsException bekomme. Immer noch keine große Sache, nicht schwer zu reparieren.

Aber ich ein wenig zu graben, und ich am Ende in einer while-Schleife in meiner merge Methode mit dem folgenden Code auf:

private static void merge(ArrayList<T> data, int first, int mid, int last) { 
    ArrayList<T> temp = new ArrayList<T>(); 
    int first1 = first, last1 = mid; 
    int first2 = mid+1, last2 = last; 
    int index = first1; 

    while (first1 <= last1 && first2 <= last2) { 
     System.out.println("still in while loop"); 
     System.out.println(data); 

     if (data.get(first1).compareTo(data.get(first2)) < 0) { 
      temp.add(index, data.get(first1)); 
      first1++; 
     } else { 
      temp.add(index, data.get(first2)); 
      first2++; 
     } 
      index++; 
      System.out.println(data); 
    } 


    while (first1 <= last1) { 
     temp.set(index, data.get(first1)); 
     first1++; 
     index++; 
    } 

    while (first2 <= last2) { 
     temp.set(index, data.get(first2)); 
     first2++; 
     index++; 
    } 

    data.clear(); 
    for (index=first; index <= last; index++) 
     data.add(index, temp.get(index)); 
} 

Die Ausgabe endet so etwas wie:

noch in while-Schleife

[8800, 2596, 7518, 9900, 7164]

[8800, 2596, 7518, 9900, 7164]

noch in while-Schleife

[2596, 8800]

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 2, Größe: 2

So etwas ist passiert zwischen der letzten Zeile vor der Schleife und den ersten beiden Zeilen in der while-Schleife, die 3 Zahlen aus meiner ArrayList löscht. Das Problem ist: Ich kann mir nicht vorstellen was. Ich entferne überhaupt keine Daten in der while-Schleife. Ich füge nur Daten zu einer anderen ArrayList hinzu. Die while-Bedingung hat nichts mit der ArrayList zu tun. Kurz gesagt, ich bin verloren.

Der Fehler ist offenbar im späteren Teil der Methode. Ich weiß immer noch nicht, was los ist, und der Stack-Trace für die IndexOutOfBoundsException zeigt immer noch auf eine Zeile in der while-Schleife (speziell if (data.get(first1).compareTo(data.get(first2)) < 0) {), aber es ist nur reproduzierbar, wenn dieser Code dort ist. Also bin ich immer noch verloren.

Was ist hier oben? Wie repariere ich es?

Answer 1

Für zukünftige Referenz war mein Problem, dass ich den Ablauf der Kontrolle nicht ordnungsgemäß verfolgt. Ich dachte, ich bleibe in der While-Schleife, aber eigentlich brach ich aus, und data.clear() war, Überraschung Überraschung, die ArrayList zu löschen. Meine Lösung, die die letzten beiden Zeilen in dem Verfahren mit ersetzen war:

for (index=first; index <= last; index++) 
     data.set(index, temp.get(index)); 

Es funktioniert jetzt.

Answer 2

Hier löscht das Problem nicht statt es wird nicht zu Temp hinzugefügt. Betrachten Szenario folgende:

Da first1 mit 0 beginnt und last1 ist Ihr Mittelwert bei 5 Elementen es 2. Auch ist, first2 beginnt mit 3 und last2 ist Ihr letzter Index seit Array von 0 beginnt es ist 4. Wenn nun first1 von 0 bis 2 geht (dh es geht in die if-Schleife) und wenn das Inkrement 3 erreicht, wird die while-Schleife beendet und first2 wird nicht verglichen, dh die andere Hälfte wird weggelassen.

So ersetzt while (first1 <= last1 && first2 <= last2) mit while (first1 <= last1 || first2 <= last2) wo wir ersetzt & & 'mit '||' wird auch zur anderen Hälfte laufen.