Merge Sort auf linearer Liste (struct-Elemente)

c.rackwitz

beschreib doch erstmal, wie mergesort funktioniert
dann schreib pseudocode

CrazyOwl

Also nach meinen Wissen läuft das ganze so ab:

1.) Als erstes wird die Quelle aufgeteilt (in meinem Fall wohl von der angegebenen Liste in 2 weitere neue Listen, so, dass dann überall die Hälfte drinnen ist)
--> dieser Punkt dürfte durch den vorgegeben Code bereits erledigt werden denke ich

2.) Danach brauch ich nochmal 2 weitere Listen (=???) um die Werte miteinander mischen zu können, dann kann ich das ganze wohl so darstellen...

|--------|
      |--- B--------|   |--- D...
A-----|        |    |
      |--- C---|    |------- E...

Das mischen der Listen würde ich also von den beiden neuen Listen B und C(in die die Elemente verteilt wurden) in die beidenen neuen und leeren Listen D und E vornehmen und dann wieder zurück in die Listen B und C, so lange bis das ganze perfekt sortiert ist.

3.) Am Ende würde ich den sortierten Inhalt aus den beiden temporären Listen wieder zurück in die anfängliche Liste A kopieren und somit wäre alles sortiert.

Meinen Pseudocode-Versuch werd ich ein wenig später posten, hab grad ziehmlichen Stress...aber er wird kommen

c.rackwitz

ähm, ich schreib mal nachher nen code, wenn alle schlafen.
in der zwischenzeit guck dir bitte mal den wikipedia eintrag dazu an. deine erklärung war mir bisschen zu konfus. sorry.

CrazyOwl

Ok vielen Dank dafür schon mal, Wikipedia werd ich mir gleich mal durchlesen. Kann sein, dass das da oben nicht so perfekt fomuliert ist, wie bereits geschrieben war vorher ziehmlich im Stress. Danke jedenfalls schon mal im Voraus.

c.rackwitz

hehe, der englische Wikipedia Artikel hat keine ordentliche Beschreibung für den Mergeschritt... werd ich heute mal noch nachbessern.
Der Mergeschritt ist aber ganz entscheidend, weil hier nicht einfach angehängt wird, sondern nochmal sortiert wird.

Also der Algorithmus ist rekursiv und von der Komplexität schneller als Quicksort.
Als Beispiel für Rekursion eines der nützlicheren Beispiele...

Ich beschreibs mal kurz:

- Daten liegen als Liste vor
- Liste wird halbiert
- für jeden der beiden Teile:
  - mehr als 2 Elemente: -> mergesort()
  - sonst: einfach sortieren (bei 2 Elementen kein Problem)
- Merge: beide Teillisten wieder zusammensetzen
  - Zeiger auf Anfangselemente beider Listen
  - kleineres Element von beiden Listen in Ergebnisliste stecken, Zeiger für diese Liste weiter; das so lange, bis beide Listen leer sind

Da wird aber der Herr Ernst keine Freude mit dir haben wenn du die Aufgabe nicht selbst versuchst

Wer sagt denn was von nicht versuchen. Nicht versuchen und nicht kapieren ist was ganz anderes...

anonymus

Mergesort haben mir in der Vorlesung vor einiger Zeit mal durchgenommen.
Ist im Script eigentlich halbwegs vernünftig erklärt:
http://vhb.fh-regensburg.de/da/

Dann auf ">>>>weiter zum Kurs".

Im sich öffnenden Fenster auf "Login"
(es werden aber keine Benutzerdaten gebraucht).

So, jetzt links noch auf "Script".
(Achtung: Popufenster zulassen, sonst kommt man ins Script nicht rein)

Auf Seite 52 (Kapitel 4.3.3) steht was zum Mergesort
(is auch ein Beispielprog dabei, glaub ich, jedoch auf nem Array implementiert)

FHS2 schrieb:

Wer sagt denn was von nicht versuchen. Nicht versuchen und nicht kapieren ist was ganz anderes...

Ich kenn dich doch...so faul wie du bist willst du es ja gar nicht versuchen :p

FHS2 schrieb:

Wer sagt denn was von nicht versuchen. Nicht versuchen und nicht kapieren ist was ganz anderes...

^

nicht versuchen IST nicht kapieren! und jetzt haltets endlich den schnabel