MergeSort iterativ mit Stacks

[info123]

Hallo an alle!

Ich soll eine iterative Variante von MergeSort mithilfe von Stacks in Pseudocode angeben.
Ich kenne MergeSort nur rekursiv und "verstehe" dementsprechend nur diese Variante.
Mein Problem fängt schon damit an, dass ich mir die iterative Variante nicht richtig vorstellen kann. Wie wird der Array geteilt, wenn der Algorithmus denn noch überhaupt so funktioniert ?

Ich bin anfangs wohl etwas naiv vorgegangen und dachte mir, dass ich mein Array teile und die rechte Hälfte im Stack ablege, dann teile ich mein linkes Teilarray und lege dessen rechte Hälfte wieder im Stack ab, usw bis nur noch ein Element im Array ist.
Dabei hat sich mir allerdings die Frage gestellt, ob meine rechten Hälften auch als Hälften im Stack abgelegt werden oder wie ein einem Array die einzelnen Arrayelemente pro Stackstelle abgelegt werden.
Jetzt gibt es zwei weitere Probleme: wie bearbeite ich die Hälften in meinem Stack und wie wende ich "merge" an, um meine Elemente am Ende wieder sortiert ausgeben zu können.

Das war so mein erster Gedanke, aber wie gesagt, ich kann nicht ganz nachvollziehen wie der Algorithmus iterativ und erst recht nicht, wie er mit Stacks funktionieren soll.

Ich hoffe mir kann das jemand erklären bzw helfen.

 

[stg]

Siehe z.B. hier: https://stackoverflow.com/a/23695092

 

[info123]

Das habe ich gefunden, aber nicht ganz verstanden.

Der Inhalt meines Array wird auf Stack1 verschoben.
Dann durchlaufe ich Stack1 und schiebe die Elemente auf die Arrays l und r. Frage: wird immer jeweils ein Element in r und l gespeichert ? In meinem weiteren Verständnis gehe jetzt davon aus:
Ich merge meine Elemente aus l und r in einen neuen Array merged und schiebe den Inhalt auf Stack2, so dass in Stack2 "Pärchen" von Zahlen sind. Nach diesem Prinzip durchlaufe ich Stack1 solange, bis ich nur noch ein Element in Stack1 habe (erste innere while-Schleife)
Jetzt durchlaufe ich mein Stack2 nach dem selben Prinzip, bis ich nur noch noch 1 Element/Paar in Stack2 habe. Das heißt ich speichere die sortierten Zahlenpaare aus Stack2 in den Arrays l und r und merge wieder alles zusammen und speichere es in Stack1 (zweite innere while schleife).

1) Warum wird abgefragt, dass Stack1 bzw Stack2 >1 Elemente im Stack haben und nicht stack.size()>0 ?
Wenn ich mir jetzt die äußere while-Schleife angucke, habe ich am Ende noch ein Element in Stack1, das wird aber in der zweiten inneren while-Schleife mit der sortieren Folge aus Stack2 gemerged, aber was ist mit dem letzten Paar in Stack2?
2) Ich verstehe den return-Befehl nicht ganz "return stack.isEmpty() ? stack2.pop() : stack.pop()"
Wird hier nacheinander zuerst aus Stack2 und dann aus Stack2 ausgeben ? Falls ja, was ist denn mit dem letzen Element aus stack2, dass nicht gemerged wurde mit dem Rest ?

Ich hoffe das ist verständlich was ich meine. Oder ich hab den Code komplett falsch verstanden. Falls dies der Fall ist, wäre es nett wenn mir das nochmal jemand erklären könnte!

 

[Xyz1]

Ich kenne MergeSort nur rekursiv und "verstehe" dementsprechend nur diese Variante.

Na statt des rekursiven Aufrufs nimmst du dann einen Stack her. Zweites Semester.

Du musst dir nur verdeutlichen was bei einem Methodenaufruf und Ende geschieht.

Ich habe eigentlich keine groß Lust das zu implementieren. Du kannst das machen.

In meinem weiteren Verständnis gehe jetzt davon aus

Man kann eigentlich erst von Verständnis sprechen wenn man es hat.
Denn sonst ist das kein Verständnis sondern ((arg)listige) Täuschung.

Noch ne Tipp ... Nein, du musst nichts in den Stack's umordnen.

 

[Meniskusschaden]

Eine Alternative wäre es, mit drei Stacks zu arbeiten. Zuerst kommen alle Elemente in Stack1. Dann werden sie in einer Schleife immer wieder zuerst von Stack1 nach Stack2 und Stack3 verschoben (split) und anschliessend wieder nach Stack1 zurück verschoben (merge). Nach dem ersten merge besteht Stack1 dann aus in sich sortierten 2er-Blöcken, nach dem zweiten merge aus 4er-Blöcken, etc. Die split- und merge-Läufe müssen dementsprechend immer blockweise organisiert werden.

 

[Meniskusschaden]

Eine Alternative wäre es, mit drei Stacks zu arbeiten.

Habe beim Joggen noch mal darüber nachgedacht. Effizienter und wahrscheinlich insgesamt naheliegender wäre es, mit vier Stacks zu arbeiten. Dann kann man die Daten wechselseitig von einem Stack-Paar in das andere verschieben und so den split- und merge-Lauf vereinen.

 

[info123]

@DerWissende
Was soll mir die Semesteranzahl sagen? Wenn ich es nicht verstehe, verstehe ich es nicht. Deswegen habe ich deutlich gefragt, ob mir das jemand erklären kann. Mir mehr oder weniger zu sagen "Ja, offensichtlich verstehst du es nicht" bringt mir leider nichts. Das weiß ich selber. Deswegen wende ich mich hier ans Forum, in der Hoffnung dass es Menschen gibt, die es besser können und mir erklären können.
Hier muss auch nichts implementiert werden, da soll "nur" einen Pseudocode her. Wie soll ich den aber angeben, wenn ich nicht verstehe bzw nicht nachvollziehen kann, wie der Algorithmus arbeitet.


@Meniskusschaden
Ich glaube ich verstehe worauf du hinaus willst, aber irgendwie auch nicht. Ich habe es glaub ich oben irgendwo erwähnt, aber mein Hauptverständnisproblem ist der ganze Vorgang des Teilens.
Ich speichere mein Array in Stack1, dann speichere ich ein Zahlenpaar in Stack2, eins in Stack3, merge jeweils Stack2 und Stack3, merge dann Stack2 UND Stack3 und speichere in Stack4 ? Das passiert dann solange, bis Stack1 leer ist oder nur noch 1Element hat und dann merge ich den Stack4 und Stack1?

 

[Meniskusschaden]

Hier ist mal ein Beispiellauf mit acht Zahlen für die Variante mit vier Stapeln. Die rechte Seite soll jeweils die zugängliche obere Seite eines Stapels sein. Wichtig ist noch, dass für Richtung von S1/S2 nach S3/S4 das jeweils kleinste Element und für die umgekehrte Richtung das jeweils größte ausgewählt wird.

S1: 1, 3, 8, 7, 4, 6, 5, 2   S3:
S2:                          S4:

abwechselnd nach S3/S4 verschieben

S1:                          S3: 2, 6, 7, 3
S2:                          S4: 5, 4, 8, 1

Richtungswechsel (grösstes zuerst)

S1: 3                        S3: 2, 6, 7
S2:                          S4: 5, 4, 8, 1

S1: 3, 1                     S3: 2, 6, 7
S2:                          S4: 5, 4, 8

Kein passendes Element => Zielstapel wechseln

S1: 3, 1                     S3: 2, 6, 7
S2: 8                        S4: 5, 4

S1: 3, 1                     S3: 2, 6
S2: 8, 7                     S4: 5, 4

S1: 3, 1                     S3: 2
S2: 8, 7, 6                  S4: 5, 4

S1: 3, 1                     S3: 2
S2: 8, 7, 6, 4               S4: 5

S1: 3, 1                     S3:
S2: 8, 7, 6, 4, 2            S4: 5

Kein passendes Element => Zielstapel wechseln

S1: 3, 1, 5                  S3:
S2: 8, 7, 6, 4, 2            S4:

Richtungswechsel (kleinstes zuerst)

S1: 3, 1, 5                  S3: 2
S2: 8, 7, 6, 4               S4:

S1: 3, 1, 5                  S3: 2, 4
S2: 8, 7, 6                  S4:

S1: 3, 1                     S3: 2, 4, 5
S2: 8, 7, 6                  S4:

S1: 3, 1                     S3: 2, 4, 5, 6
S2: 8, 7                     S4:

S1: 3, 1                     S3: 2, 4, 5, 6, 7
S2: 8                        S4:

S1: 3, 1                     S3: 2, 4, 5, 6, 7, 8
S2:                          S4:

Kein passendes Element => Zielstapel wechseln

S1: 3                        S3: 2, 4, 5, 6, 7, 8
S2:                          S4: 1

S1:                          S3: 2, 4, 5, 6, 7, 8
S2:                          S4: 1, 3

Richtungswechsel (grösstes zuerst)

S1: 8                        S3: 2, 4, 5, 6, 7
S2:                          S4: 1, 3

S1: 8, 7                     S3: 2, 4, 5, 6
S2:                          S4: 1, 3

S1: 8, 7, 6                  S3: 2, 4, 5
S2:                          S4: 1, 3

S1: 8, 7, 6, 5               S3: 2, 4
S2:                          S4: 1, 3

S1: 8, 7, 6, 5, 4            S3: 2
S2:                          S4: 1, 3

S1: 8, 7, 6, 5, 4, 3         S3: 2
S2:                          S4: 1

S1: 8, 7, 6, 5, 4, 3, 2      S3:
S2:                          S4: 1

S1: 8, 7, 6, 5, 4, 3, 2, 1   S3:
S2:                          S4:

 

[Xyz1]

Was soll mir die Semesteranzahl sagen?

Vielleicht auch drittes Semester.

nicht nachvollziehen kann, wie der Algorithmus arbeitet

Ja das ist ein Problem. Nimm dir ne Kartenspiel mit 10 Karten her - und spiel es durch.

Oder verstehst du gaaaar nichts? Dann zum Abdecker.

 

[Xyz1]

Hier ist mal ein Beispiellauf mit acht Zahlen für die Variante mit vier Stapeln.

Der Schaden war mir (weit) voraus....

 

[Meniskusschaden]

Der Schaden ...

Musste erst mal überlegen, was du meinst, bis mir aufgefallen ist, dass ich ja ein Subtyp von Schaden bin.

 

[Xyz1]

Hier ist mal ein Beispiellauf mit

Habe es mir durchgelesen. Bewegt sich schon etwas weit weg vom MergeSort....
Meiner bescheidenen Meinung nach, braucht es (auch unter Beibehaltung der "inplacestizität") n ( n/2) Stacks.

 

[Meniskusschaden]

Bewegt sich schon etwas weit weg vom MergeSort....

Näher am Mergesort kann man kaum sein. Man sieht doch fast schon die Magnetbandspulen rotieren.

(auch unter Beibehaltung der "inplacestizität")

Mergesort läuft normalerweise ohnehin nicht in-place.

 

[Xyz1]

dass ich ja ein Subtyp von Schaden bin.

Ganz zufällig weiß ich das mit dem Meniskusschaden was das ist.

Mergesort läuft normalerweise ohnehin nicht in-place.

Es kommt nun darauf an wie streng oder laissezfaire man in-place definiert. Aber ja du hast Recht MergeSort ist nicht in-place. Mein Fehler.