Mergesort

[Crite]

Hallo,
Ich bin gerade ziemlich am Verzweifeln.
Ich soll den mergesort selber coden, hab zwar ansatzweise was geschaft, aber er funktioniert nicht.

Das liegt wahrscheinlich auch daran, dass ich ihn nicht verstehen, zumindest soweit nicht , dass ich ihn umsetzten kann.

Ich weiß, dass man ein Array soweit teilt bis auf einer Seite ein Element übrig ist und die dann vergleicht.
Dann setzt man die zusammen und vergleicht das mit einem anderen bereits zusammengefügtes, usw.

Allerdings weiß ich gar nicht, wie das geht mit der Rekursion und wie das Zusammenfügen passiert, geschweige das Splitten.
Und wie groß ist das Hilfsarray, wenn ich das erste Array soweit zerlegt habe, bis nur noch 1 Element übrig ist (ist es immer so groß, wie das eingefügte Array oder variiert es?)

Könnte mir jemand erklären, ab wann gesplittet wird( vorallem wie), wann ich nur noch ein Element auf einer Seite habe und wann zusammengefügt wird. Ach und wie groß das Hilfsarray zu dem Zeitpunkt ist.

Ich hoffe wirklich, dass mir jemand den mergesort ausührlich beschreiben kann, die sonstigen Seiten mit beispielcode helfen mit nicht weiter. <wie gesagt, am Verzweifeln>

Gruß

 

[RedGreenBlue]

Schau mal bitte zuerst hier: Mergesort

Anschauerlicher und strukturierter (nebst Quellcode) wird es dir kaum jemand erklären können. Sollten dennoch Verständnis- oder Implementierungsfragen auftreten, frage hier nochmals nach.

LG, RGB

 

[Crite]

Die Methode merge mischt die beiden Hälften des Arrays(soweit diese sortiert sind).
Aber ich verstehe nicht, wo im Programm die einzelnen Hälften sortiert werden?

 

[RedGreenBlue]

Allgemeiner Hinweis: Mittels Bildschirmausgaben kann man alle Algorithmen sich selbst erschließen.

Für deinen Fall habe ich provisorisch an den wichtigsten Stellen Ausgaben hinzugefügt [Paste, Copy und Ausführen]:

public class MergeSorter
{
  private int[] a;
  private int[] b;    // Hilfsarray
  private int n; 
  
  public static void main(String args[]){
    int[] c = {9,5,1,3,7,5,1};
    MergeSorter s=new MergeSorter();
    s.sort(c);
  }
  
  public void sort(int[] a)
  {
    this.a=a;
    n=a.length;
    b=new int[n];
    mergesort(0, n-1);
  }
  
  private void mergesort(int lo, int hi)
  {
    System.out.println("mergesort: " + " lo:" + lo + " hi:" + hi);
    if (lo<hi)
    {
      int m=(lo+hi)/2;
      System.out.println("lo,m");
      mergesort(lo, m);
      System.out.println("m+1,hi");
      mergesort(m+1, hi);
      System.out.println("MERGE: lo=" + lo +" m= "+ m + " hi= " + hi);
      merge(lo, m, hi);
    }
  }
  
  private void merge(int lo, int m, int hi)
  {
    int i, j, k;
    // beide Hälften von a in Hilfsarray b kopieren
    System.out.print("Teil von A-Array vor Sortierung: ");
    for (i=lo; i<=hi; i++)
    {b[i]=a[i];
      System.out.print(+ a[i]+ " ");
    }
    System.out.println();
    
    i=lo; j=m+1; k=lo;
    // jeweils das nächstgrößte Element zurückkopieren
    while (i<=m && j<=hi)
    if (b[i]<=b[j])
    a[k++]=b[i++];
    else
    a[k++]=b[j++];
    
    // Rest der vorderen Hälfte falls vorhanden zurückkopieren
    while (i<=m)
    a[k++]=b[i++];
    System.out.print("Teil von A-Array nach Sortierung: ");
    for (i=lo; i<=hi; i++)
    System.out.print(a[i]+ " ");
    System.out.println();
  }
}    // end class MergeSorter

Durch die Ausgabe zeigt sich, dass folgendes Teilstück der Methode merge(int lo, int m, int hi) für die Sortierung verantwortlich ist:

// jeweils das nächstgrößte Element zurückkopieren
    while (i<=m && j<=hi)
    if (b[i]<=b[j])
    a[k++]=b[i++];
    else
    a[k++]=b[j++];

LG, RGB

Sollte noch etwas unklar sein, so bitte erneute Nachfrage!

 

[Crite]

Vielen Dank.
Mein Problem war, dass ich keine Hilfsvariablen benutzt habe.
Ich weiß selber nicht, wieso ich das nicht gesehen habe, obwohl ich das gefühlte 1000 mal durch den Debugger geschoben hab......
Aber gut, danke nochmals.