MergeSort Problem

[comastyle]

Hallo Leute

Brauche Hilfe bei den ersten schweren Schritten mit komplexeren Algorithmen. Ich möchte ein Array mit MergeSort sortieren, nur bekomme ich in einer Zeile immer wieder ArrayOutOfBounds Fehler. Ich weiß nicht mehr weiter... Debugger versucht, Zettel und Papier.... einfach nur nervtötend

Schreiben tu ich mit BlueJ

Vielen Dank im Vorraus

Bye Alex

    public void MergeSort()
     {
        start();
        ms(0, feld.length - 1);
        zeitnahme("MergeSort");
               
     }
     
     public void ms(int links, int rechts)
     {
         if(links < rechts)
         {
             mitte = (links + rechts) / 2;
             ms(links, mitte);
             ms(mitte + 1 , rechts);
             merge(links, mitte, rechts);
         }
     
      }     
      
      public void merge(int links, int mitte, int rechts)
      {
          
          
          n = feld.length;
          tmpfeld = new int[(n + 1)/ 2];
          
          int i;
          int j;
          int k;
          
          i = 0;
          j = links;
          //Erste Hälfte von feld[] in tmpfeld[] kopieren
          while(j <= mitte)
              tmpfeld[i++] = feld[j++];
              
          
          i = 0;
          k = links;
        
          //Das nächstgrößte Element zurückkopieren
          while(k < j && j <= rechts)
              if(tmpfeld[i] <= feld[j])
                  feld[k++] = tmpfeld[i++];
              else
                 feld[k++] = tmpfeld[j++];  <-- Hier ist der Fehler ArrayOutOfBoundsExeption 25 - 
weiß beim besten willen nicht wieso ich nen ungültigen Index dort habe
                  
          //Wenn Rest von tmpfeld[] vorhanden - zurückkopieren
          while(k < j)
              feld[k++] = tmpfeld[i++];
      }

 

[SlaterB]

wenn du zehn Dinge in einer Zeile gleichzeitig machst, bist du selber schuld,
dann ist z.B. die Exception wenig gehaltvoll, da du nicht weißt,
welches Array gemeint ist

auf Klammern zu verzichten ist noch ein Riesenfehler..


also

else
       feld[k++] = tmpfeld[j++];

->

else {
   k++;
   j++;
   int x = tmpfeld[j];
   feld[k] = x;
}

so, dann machst du

else {
   k++;
   j++;
   if (j >= tempeld.length) {
       throw new RuntimeException("j ist: "+j+", tempfeld ist: "+tempfeld.length);
   }
   int x = tmpfeld[j];
   feld[k] = x;
}

bzw.

else {
   if (j >= tempeld.length) {
       throw new RuntimeException("j ist: "+j+", tempfeld ist: "+tempfeld.length);
   }
   int x = tmpfeld[j];
   feld[k] = x;
   k++;
   j++;
}

und weiß erstmal was los ist,


ich vermute dass du
j < rechts
statt
j <= rechts
schreiben musst,

oder durch das ++ wird j sogar größer als die Grenze rechts?
durch die RuntimeException (oder System.out.println) kinderleicht herauszufinden

was ist rechts, wie lang ist das Array?

 

[comastyle]

Danke erstmal

Throw Exeption hab ich bisher noch nicht benutzt - aber man lernt ja immer dazu

"rechts" ist "feld.length -1"

"tmpfeld" ist '"(feld.lenght +1) /2"

wenn ich also zu anfang ein




das array wird ganz zu anfang mit einer Abfrage erzeugt - dies ist ein Auszug aus nem Programm mit mehreren Sortierverfahren die auch alle Funktionieren.

 

[comastyle]

oh weia - da ist irgendwas ganz böse durcheinander - beste ist wohl ich versuchs nochmal von vorne . sind mehrere fehlerhafe arrayabfragen dabei - aber trotzdem danke

 

[Gelöschtes Mitglied 5909]

http://www.sortieralgorithmen.de/

 

[comastyle]

Danke - Habs nun geschafft