MergeSort

[Neu_ling]

Hallo Community,

ich komme beim programmieren eines MergeSort-Algorithmus nicht weiter. Es handelt sich hierbei nur um die Methode mergeSort, die scheinbar nicht klappt. Die Methode merge funktioniert. Ich hoffe ihr könnt einen Fehler entdecken. Ich bekomme bei kleinen Zahlenfolgen(2 Ziffern), das korrekt sortierte Ergebnis heraus. Nur bei mehr Ziffern, werden nur einzelne Zahlen vertauscht.

Mfg Neu_Ling

public static int[] sortRekursiv(int[] a) {
    int b=0;

    if (a.length == 1) {
        return a;
          }

      int[] links = new int[a.length / 2];
      int[] rechts = new int[a.length - links.length];
      int index = 0;

       while (index < links.length) {
            links[index] = a[index];
              index++;
                  }

       while (index < a.length) {
            rechts[b] = a[index];
              index++;
              b++;

              }


              sortRekursiv(links);
              sortRekursiv(rechts);

                return merge(links, rechts);
                        }

 

[SlaterB]

ohne in diesem Fall den Fehler zu verraten:
schau dir doch ganz einfach an, was dein Programm macht, mit einem 3er-Array dürftest du nicht gerade überschwemmt werden,
System.out.println() oder ein Debugger helfen dir,

gibt zu Beginn der Methode das Array des Parameters aus (Arrays.toString() oder eine Hilfsmethode)
dann die Länge der beiden Arrays,
dann die befüllten Arrays, evtl. in den Schleifen genau verfolgen wie sich Index, a, b entwickeln

wenn du das alles machst siehst du schon Fehler,
ob du dann noch selbstständig zur Korrektur kommst ist nicht 100% sicher,
aber schon ein ganz anderer Stand als nur den Code zu posten und völlig zu rätseln

so wirst du bei 100 Programmen noch 300 Fehler finden, oder 300 Mal im Forum fragen müssen, deine Wahl
(bei ersten Posting vielleicht bisschen früh viel verlangt, aber früh übt sich, gute Gelegenheit )

edit:
oh, mein vermuteter Fehler ist gar nicht da, weiß gar nicht ob jetzt ein Fehler vorliegt, sieht geradezu richtig aus,

vollständigeres Programm mit merge ließe sich eher testen (also das was ich zuvor beschrieb )
falls nicht von dir zu finden


edit2:
jetzt habe ich wieder einen, bisschen vertracker als ich zuerst im Sinne hatte, da will ich es lieber sagen:
du ignorierst die Rückgabewerte, die sortierten Arrays, innerhalb der Rekursion (Zeile 25+26)

 

[Landei]

Wenn du eine IDE wie NetBeans oder Eclipse verwendest, ist das eine großartige Gelegenheit zu lernen, wie ein Debugger funktioniert. Falls nicht, kannst du dir mit [c]System.out.println()[/c] interessante Werte wie Schleifenvariablen ausgeben lassen, und damit nachvollziehen, was schief läuft. Den aktuellen Zustand des Arrays bekommst du mit [c]java.util.Arrays.toString(meinArray)[/c] ausgegeben.

 

[Neu_ling]

@SlaterB Wo ignoriere ich die Rückgabewerte denn? Ich rechne doch ganz normal mit ihnen weiter oder nicht? Stehe auf dem Schlauch...

@Landei Wo genau müsste ich System.out.println() denn einfügen? Tut mir Leid für die dumme Frage.

 

[faetzminator]

@SlaterB Wo ignoriere ich die Rückgabewerte denn? Ich rechne doch ganz normal mit ihnen weiter oder nicht? Stehe auf dem Schlauch...

Z25 und 26 ?

 

[Neu_ling]

Ich verstehe nicht, was du mit ignorieren meinst. Auf welche Arrays soll ich die Methode denn sonst rekursiv weiteranwenden?

 

[Landei]

Na wo kannst du denn sehen, dass etwas falsch läuft? Z.B. kannst du dir links und rechts vor und nach dem rekursiven Aufruf anzeigen lassen. Und dann schaust du z.B. ob nur eines der Teilarrays betroffen ist, zeigst beim nächsten Versuch die entsprechenden Schleifenvariablen an u.s.w.

Aber wie gesagt, die bessere Lösung ist ein Debugger.

 

[SlaterB]

wenn im ersten Schritt ein 3er Array 4,3,2
in 4 und 3,2 aufgetrennt wird,
dann liefert
sortRekursiv(rechts);
ein sortiertes Array 2,3 zurück, 'rechts' selber ist aber nach wie vor 3,2, verwende den Rückgabewert des Aufrufs

System.out.println() kommt letztlich überall hin, eben um z.B. anzuschauen wie 'rechts' nach dessen Sortierung aussieht

 

[Neu_ling]

Okay, es funktioniert endlich! Danke für die Antworten!