Merge-Algorithmus

[rosima26]

Habe die Methode schon 3 mal neu geschrieben und das hat nie funktioniert... Nerven sind am Ende

 

[yfons123]

Habe die Methode schon 3 mal neu geschrieben und das hat nie funktioniert... Nerven sind am Ende

meine Datenstruktur professorin hat mal versucht einen eigenen merge zu schreiben und konnte es nach 5 stunden lösen

also denk dir nichts dabei..

 

[Jw456]

meine Datenstruktur professorin hat mal versucht einen eigenen merge zu schreiben und konnte es nach 5 stunden lösen

also denk dir nichts dabei..

Der TE will doch was lernnen. Da finde ich so eine Antwort nicht hilfreich.

Wie schon gesagt wurde hat er ja schon eine Methode die zwei sortierte Arrays mergen kann. Also was liegt da näher als dise in der Methode wo vier Arrays verbunden werden sollen zu benutzen.

Warum alles in einer Methode machen.

 

[KonradN]

Habe die Methode schon 3 mal neu geschrieben und das hat nie funktioniert... Nerven sind am Ende

Also ggf. hilft da, erst einmal etwas Abstand. Man kann gewisse Dinge nicht erzwingen.

Und wenn man dann mit ruhigen Kopf heran geht, dann hilft aus meiner Sicht ausschließlich:
a) Den Ablauf im Detail durchgehen. In der Regel ist eine graphische Darstellung am sinnvollsten. Spiel den Prozess durch!
b) Beschreibe den Prozess. Dabei unterteilst Du den Prozess in Teilprozesse! Das ermöglichst Dir, den Überblick zu behalten! Sowohl jetzt als auch dann später bei der Umsetzung.
c) Dann - und erst dann - schreibst Du das Programm

Geh diese Schritte durch. Und wirklich diese Schritte. Das ist und bleibt der Weg, wie man einen Sachverhalt entwickeln kann. Dieser Prozess wird immer, aber auch wirklich immer, angewendet von mir. Ich schreibe in der Regel nicht eine Zeile Code ohne eben genau diese Schritte! Das läuft meist nur im Kopf ab, aber sobald die Sachverhalte etwas komplizierter werden, dann brauche ich auch Skizzen und ähnliches. Schmierzettel sind ein wichtiges Arbeitsgerät von mir!

Daher wäre mein Ratschlag, endlich genau diese Arbeitsweise zu adaptieren. Also beschreibe genau, was Du für eine Eingabe bekommst (Vermutlich die 5 Arrays - 4 Source Arrays mit Grenzen, die zu behandeln sind und ein Ziel-Array mit Grenzen, wo die Daten hin sollen).
Und dann beschreibe das Vorgehen!

Ich weiss nicht, wie weit ihr mit den Klassen seid - es wird deutlich einfacher, wenn man eigene Klassen schreibt, die gewisse Dinge kapseln. Ein Array mit den start und ende Indices gehören zusammen und die könnte man z.B., Kapseln. Dieses Kapseln vereinfacht es, da man hier jetzt Objekte erstellt, mit denen man arbeiten kann. Es wird also deutlich weniger abstrakt. Wenn das bei Euch nicht geht, dann machst Du es nicht bei der Umsetzung - aber bei der Visualisierung nutzt Du es dennoch. Dann hast Du Sourcen und das sind halt Arrays mit Start und Ende. Und da Du nacheinander die Elemente lesen willst, hast Du da dann halt einen Index "current" oder so. Damit kannst Du dann arbeiten.

Und dann wird es sehr einfach. Der bisherige merge Algorithmus mit den zwei Elementen war einfach:

1. So lange beide Source Arrays noch zu verarbeitende Elemente haben:
1.1 Vergleiche die nächsten beiden Elemente, das kleinere Element verarbeitest Du.
2. Übertrage die restlichen Elemente der beiden Source Arrays.

Element Verarbeiten ist dabei:
1. Das Element merken, den index des Source Arrays erhöhen
2. Das gemerkte Element im Ziel einfügen und den index des Ziel-Arrays erhöhen.

Das ist die ganze Beschreibung.

Und nun hast Du mehrere Optionen, wie Du vorgehen kannst:
a) Für beliebige Anzahl von Merges kann man einfach in einer Schleife so lange das kleinste Elemente aller Sourcen suchen, bis es keines mehr gibt. Das kleinste Element würde dann durch versetzen des jeweiligen Indices entnehmen und im Ziel einfügen.
b) 4 = 2*2 - Du kannst also einfach den bisherigen Algorithmus einfach 3 mal anwenden.

Beides ist nicht besonders kompliziert und die Beschreibung ist ja schon genannt. Das muss man dann nur noch verfeinern.

Wichtig ist ggf. das Handling. Dazu muss man dann bei beiden Dingen etwas machen.

Bei a) Da Du hier vermutlich alles als Parameter hast, ist das sehr schwer zu handhaben. Wenn du 4 Sourcen hast jeweils mit array, linker index, rechter index, dann kannst Du damit nur schlecht arbeiten in Schleifen und so. Daher kannst Du das einfach in ein Array packen. Also erstell ein Array von Arrays und pack da die Source Arrays rein. Ein Array für die start Indices und ein Array für die Ende Indices. Schon kannst Du da mit Schleifen drüber arbeiten und z.B. feststellen, an welcher Position das nächste kleinste Element ist. Dieses kann man dann auslesen, den Index verändern u.s.w.

Bei b) Hier ist das Problem ggf. dass Du ein Zielbereich für die Merges brauchst. Das ist bei der Lösung unschön. Du musst also ein oder zwei Arrays erstellen, in die du zuerst merged. Dann merged du von diesen in den Zielbereich. Ob ein Array mit zwei Teilbereichen oder zwei Arrays ist dabei vollkommen egal.