Anzeige

Benötige dringend Hilfe zu mergeSort()

#1
Hallo,
ich sollte für die FH im Rahmen eines Tutoriums eine Aufgabe programmieren.
Das habe ich gemacht, allerdings war der Code nicht lauffähig.
Der Prof hat mir dann seinen Ansatz für diese Aufgabe geschickt, da bekomme ich jedoch ne ArrayIndexOutofBound exception.
Da bin gerade in der Klausurvorbereitung für andere Fächer und ziemlich im Stress bin, möchte ich euch um Hilfe bitten.
In den kommentaren stehen die Aufgabenstellungen

Java:
public class Sortieren {
   
   private int[] zahlen = { 12501, 88, 409, 0, 1587, 1412 };

 
   //1. sort() ruft mergeSort(int from, into to) auf
   public void sort() {
       mergeSort(0, zahlen.length - 1);
   }

   private void mergeSort(int from, int to) {
   //2. mergeSort()terminiert ohne weitere Aktionen, falls from >=to, denn 0 oder 1 Elemente
       //sind schon sortiert
       
           if (from < to) {
               //3. falls from<to, ruft mergeSort() rekursiv mergeSort() für die Hälften from bis x und
               // x+1 bis to auf. Nach Rückkehr aus den rekursiven Aufrufen sind beide Haelften sortiert
               mergeSort(from, from + (to-from) / 2);
               mergeSort(from + (to - from) / 2+1,to);
               
               //4. In ein temporäres int-Array werden der Reihe nach jeweils die Elemente beider Hälften
               // kopiert. Es wird immer das nächste Element genommen, welches das kleinere beider Hälften
               //ist.
               int[] temp = new int[to-from-1];// Da kommen sie sortiert
                                                   // wieder rein
               int index = 0;
               int ersteHaelfte2 = from;
               int zweiteHaelfte = from + (to - from) / 2 +1;

               for (int ersteHaelfte = from; ersteHaelfte <= from + (to-from) /2;ersteHaelfte++) {
                   while ((zweiteHaelfte<=to)
               && (zahlen[zweiteHaelfte] < zahlen[ersteHaelfte])) {

                       temp[index] = zahlen[zweiteHaelfte];
                       zweiteHaelfte++;
               index++;

               }

               if((zweiteHaelfte>to) || (zahlen[ersteHaelfte]< zahlen[zweiteHaelfte])){
                   temp[index] = zahlen[ersteHaelfte];
                   //ersteHaelfte++;
                   index++;
               }

               
           }
               while (zweiteHaelfte<=to){
                   temp[index] = zahlen[zweiteHaelfte];
                   zweiteHaelfte++;
                   index++;
               }
           //5. Die sortierte Folge aus dem temporären int-Array wird
               //wieder zurückkopiert in das ursprüngliche Array
               System.arraycopy(temp, 0, zahlen, from, temp.length);
               
       }
   }
}
 

Yaslaw

n/a
Moderator
#2
Und wo kommt der Fehler?

Nachtrag:
zählst du da nicht einmal -1 zuviel ab?
Java:
mergeSort(0, zahlen.length - 1);
...
//from ist bereits array-Länge -1 Warum ziehst du da nochmals 1 ab?
int[] temp = new int[to-from-1];// Da kommen sie sortiert
 

zerix

Hausmeister
Moderator
#3
Hallo User89,

generell ist so ein Forum da um Hilfestellungen zu geben und nicht, um die Fehler zu suchen und somit dem Thread-Ersteller die Arbeit abzunehmen, nur weil er keine oder kaum Zeit. Denn die Leute hier sind auch entweder berufstätig oder studieren auch oder wie in meinem Fall sogar beides. ;-)
Deshalb wäre es ja schon mal nicht schlecht, wenn du auch mal die Fehlermeldung posten würdest. So sieht man zumindest mal, wo der Fehler auftritt.


Viele Grüße
Sascha
 
#4
Erstmal danke für eure Anteilnahme
zerix das respektiere ich!

@Yaslaw
Das ist auch die Stelle bei der die Exception auftritt
Glaube du hast recht. Wenn ich allerdings "-1" entferne wird nach der Zuweisung in Zeile 34 " temp[index] = zahlen[zweiteHaelfte];"
erneut eine IndexOutofBound geworfen....das verstehe ich nicht....
die Fehlermeldungen lauten dann:
"main" java.lang.ArrayIndexOutOfBoundsException: 1
Sortieren.mergeSort(Sortieren.java:45)
Sortieren.mergeSort(Sortieren.java:22)
Sortieren.mergeSort(Sortieren.java:22)
Sortieren.sort(Sortieren.java:12)
Test.main(Test.java:8)
 

Yaslaw

n/a
Moderator
#5
Keine Ahnung. Weil du beim definieren von zweiteHaelfte wieder1 dazu rechnest?

Schalte den Debuger ein und schaue, was für Werte deine Variablen haben.
Müsste ich auch so machen. Alles andere gibt sinnloses Kopfzerbrechen.
 

zerix

Hausmeister
Moderator
#6
Hallo,

ich habe es nicht getestet. Aber ich denke du hast einen Fehler.
Irgendwann wird mergeSort bei dir mit den Indizes 0 und 1 aufgerufen.
Dann ist diese Array-Länge = 1
Code:
 int[] temp = new int[to-from];
Du hast aber zwei Zahlen, die gespeichert werden müssen, nämlich die an Index 0 und die an Index 1. Das passt nicht. ;-)

Viele Grüße
Sascha
 
Anzeige

Neue Beiträge

Anzeige