Merge-Algorithmus

rosima26

rosima26

Aktives Mitglied
Moin, ich verstehe eine Methode aus dem Merge-Algorithmus leider überhaupt nicht und wäre sehr dankbar wenn jemand versuchen könnte, mir zu sagen was in der Methode vor sich geht... Das Array wird quasi in einer anderen Methode schon zerlegt und soll hier wieder zusammengeführt werden, jedoch verstehe ich nicht wirklich was da passiert.
Danke schonmal 😘
Java: 
public void merge(T[] a, int l1, int r1, T[] b, int l2, int r2, T[] c, int l3) {
        while (l1 < r1 && l2 < r2)
            c[l3++] = (a[l1].compareTo(b[l2]) < 0) ? a[l1++] : b[l2++];
        while (l1 < r1)
            c[l3++] = a[l1++];
        while (l2 < r2)
            c[l3++] = b[l2++];
 
ich würde dir raten dass du dir ein deck von spiel karten nimmst und da den merge algorithmus mal per hand durchführst beste art und weise es durchzufführen zum verstehen

du hast zb zwei häufchen die ja sortiert sind durch die zerlegung und bausst sie zusammen

zb
9 K A A
Zum Vergrößern anklicken....
und
7 8 K A
Zum Vergrößern anklicken....
dann stöpselst du es wieder zusammen

du nimmst das kleinste immer von den stapeln
also wächst dein sortierter stapel so
7
Zum Vergrößern anklicken....
7 8
Zum Vergrößern anklicken....
7 8 9
Zum Vergrößern anklicken....
7 8 9 K
Zum Vergrößern anklicken....
gleichheit von K also einfach gleich mit
Zum Vergrößern anklicken....
7 8 9 K K
Zum Vergrößern anklicken....
gleiche beim Ass
7 8 9 K K A A A
Zum Vergrößern anklicken....
das machst du mit deinen anderen stapeln auch

dann hast du insgesamt 4 stapel mit jeweils 8 karten
und da machst du das gleiche wieder

du stöpselst immer zusammen ohne nachzudenken, das ist der trick beim merge...teile es auf auf mini probleme die sich selbst lösen
die aufteilung wurde von meinem prof immer als "teile und herrsche" beschriebne 😀
 
dann benenne die variablen um und mach clean code daraus, so eine variablen benennung ist halt absolut beschissen... niemand kann das auf anhieb lesen
 
Habe Schwierigkeiten damit, zu verstehen was da abgeht. Könnte mir das vielleicht jmd ganz kurz Zeile für Zeile erklären? Muss den Code umschreiben und dazu sollte ich verstehen was die Methode in jeder Zeile macht...
 
Java: 
/** Kopiert zwei Bereiche aus den Arrays a und b in sortierter Reihenfolge nach c.
  *
  * Vorbedingung: die Elemente in den Arrays a und b sind wenigstens in 
  * den angegebenen Bereichen bereits sortiert.
  * 
  * @param a  erstes Quellarray
  * @param l1 Index des nächsten zu kopierenden Elements aus a
  * @param r1 Ende (exkl.) des zu kopierenden Bereichs aus a
  * @param b  zweites Quellarray
  * @param l2 Index des nächsten zu kopierenden Elements aus b
  * @param r2 Ende (exkl.) des zu kopierenden Bereichs aus b
  * @param c  Zielarray
  * @param l3 Index, ab dem in c eingefügt werden soll
  */
public void merge(T[] a, int l1, int r1, T[] b, int l2, int r2, T[] c, int l3) {
        // so lange es im Array a UND im Array b noch zu kopierende Elemente gibt, wiederhole
        while (l1 < r1 && l2 < r2)
            // Falls das zu kopierende Element aus a kleiner als das zu kopierende Element aus b ist,
            // lege das zu kopierende Element aus a, sonst das zu kopierende Element aus b
            // am aktuellen Einfügeindex in c ab. Erhöhe dementsprechend den Index des 
            // nächsten zu kopierenden Elements für a (l1) oder für b (l2), außerdem den
            // Einfügeindex (l3).
            c[l3++] = (a[l1].compareTo(b[l2]) < 0) ? a[l1++] : b[l2++];
 
        // Nach der Schleife sind alle Elemente aus wenigstens einem Quellarray vollständig kopiert,
        // so dass die restlichen Elemente einfach nach c kopiert werden können.

        // So lange es im Array a noch zu kopierende Elemente gibt, kopiere diese nach c
        while (l1 < r1)
            c[l3++] = a[l1++];
        // So lange es im Array b noch zu kopierende Elemente gibt, kopiere diese nach c
        while (l2 < r2)
            c[l3++] = b[l2++];
 
Vielen lieben Dank das hilft mir sehr. Hast du vielleicht noch einen Tipp wie ich die erste While Schleife umschreiben könnte, dass das mit 4 anstatt 2 Arrays gemacht wird? Brauche keinen expliziten Code aber ein Tipp wäre super, sitze jetzt ewig dadran
 
Bei so Aufgaben kann ich nur immer wieder empfehlen: Spiele es einmal durch!
Du hast also 4 Reihen mit Zahlen, die alle für sich sortiert sind. Und nun willst die Zahlen in einer Reihenfolge zusammen führen. Kriegst Du das irgendwie hin?

Also ich gebe Dir 4 Zettel. die jeweils haben:
1. Zettel: 7, 9, 11
2. Zettel: 3, 8
3. Zettel: 1
4. Zettel: 10, 12, 14, 27

Also: Schaffst Du es, das irgendwie zusammen zu kriegen, so dass da du dann ein Zettel mit 1, 3, 7, 8, 9, 10, 11, 12, 14, 27 hast?
Kannst Du den Weg beschreiben? Beschreibe den Weg so, dass es andere nur mit der Beschreibung richtig hin kriegen.

Wenn Du das schaffst, dann kannst Du über die Umsetzung in Java nachdenken.
 
mihe7 hat gesagt.:
Ich wage zu bezweifeln, dass Du das tun sollst. Wie lautet denn die genaue Aufgabenstellung?
Zum Vergrößern anklicken....
Ich meine, dass es tatsächlich so Aufgaben gab. Statt aufteilen in 2 Bereiche dann Aufteilen in n Bereiche bei QuickSort ... Wobei ich mich da durchaus irren kann. Aber das ist prinzipiell egal - Das kann man sehr gut als Übung nehmen, wie man an das Schreiben eines Programmes heran geht. Und das ist und bleibt immer das Gleiche: Fachliche Anforderung / Vorgehen verstehen und dann nur noch 1:1 umsetzen.
 
Also die Aufgabe ist sozusagen das Array 4 zu teilen und dann wieder zusammenzusetzen, funktioniert folglich auch nur mit length = 4er Potenzen.
Habe jetzt Code geschrieben der fast perfekt funktioniert aber eben nur fast 😪
 
rosima26 hat gesagt.:
Also die Aufgabe ist sozusagen das Array 4 zu teilen und dann wieder zusammenzusetzen, funktioniert folglich auch nur mit length = 4er Potenzen.
Habe jetzt Code geschrieben der fast perfekt funktioniert aber eben nur fast 😪
Zum Vergrößern anklicken....
Verwende doch einfach die bestehende merge-Methode:

a) merge die ersten zwei Arrays in ein neues Array x,
b) merge die zweiten zwei Arrays in ein neues Array y
c) merge x und y zum finalen Array.

Done.
 
KonradN hat gesagt.:
Ich meine, dass es tatsächlich so Aufgaben gab. Statt aufteilen in 2 Bereiche dann Aufteilen in n Bereiche bei QuickSort ...
Zum Vergrößern anklicken....
Das ist durchaus möglich und ich will da auch gar nichts ausschließen. Mich hat nur der Sprung von 2 auf 4 hellhörig werden lassen; wenn es um n-Arrays gegangen wäre, dann hätte ich das auch anders gesehen. Jedenfalls wäre die genaue Aufgabenstellung hilfreich gewesen 🙂
 
Da bin ich grade dran. Habe gestern das geschrieben, die innersten 6 Zahlen des Arrays werden aber nicht sortiert
Java: 
while (l1 < r1 && l2 < r2)
            a[l5++] = (b[l1].compareTo(c[l2]) < 0) ? b[l1++] : c[l2++];
        while (l1 < r1 && l3 < r3)
            a[l5++] = (b[l1].compareTo(d[l3]) < 0) ? b[l1++] : d[l3++];
        while (l1 < r1 && l4 < r4)
            a[l5++] = (b[l1].compareTo(e[l4]) < 0) ? b[l1++] : e[l4++];
        while (l2 < r2 && l3 < r3)
            a[l5++] = (c[l2].compareTo(d[l3]) < 0) ? c[l2++] : d[l3++];
        while (l2 < r2 && l4 < r4)
            a[l5++] = (c[l2].compareTo(e[l4]) < 0) ? c[l2++] : e[l4++];
        while (l3 < r3 && l4 < r4)
            a[l5++] = (d[l3].compareTo(e[l4]) < 0) ? d[l3++] : e[l4++];
        while (l1 < r1 && l2 < r2 && l3 < r3) {
            T temp;
            T temp2;
            T temp3;
            temp = (b[l1].compareTo(c[l2]) < 0) ? b[l1++] : c[l2++];
            temp2 = (c[l2].compareTo(d[l3]) < 0) ? c[l2++] : d[l3++];
            temp3 = (b[l1].compareTo(d[l3]) < 0) ? b[l1++] : d[l3++];
            if ((temp.compareTo(temp2) < 0) && (temp.compareTo(temp3) < 0)) {
                a[l5++] = temp;
            }
            else if ((temp2.compareTo(temp3) < 0) && (temp2.compareTo(temp) < 0)) {
                a[l5++] = temp2;
            }
            else if ((temp3.compareTo(temp) < 0) && (temp3.compareTo(temp2) < 0)) {
                a[l5++] = temp3;
            }

        }
        while (l1 < r1 && l2 < r2 && l4 < r4) {
            T temp;
            T temp2;
            T temp3;
            temp = (b[l1].compareTo(c[l2]) < 0) ? b[l1++] : c[l2++];
            temp2 = (c[l2].compareTo(e[l4]) < 0) ? c[l2++] : e[l4++];
            temp3 = (b[l1].compareTo(e[l4]) < 0) ? b[l1++] : e[l4++];
            if ((temp.compareTo(temp2) < 0) && (temp.compareTo(temp3) < 0)) {
                a[l5++] = temp;
            }
            else if ((temp2.compareTo(temp3) < 0) && (temp2.compareTo(temp) < 0)) {
                a[l5++] = temp2;
            }
            else if ((temp3.compareTo(temp) < 0) && (temp3.compareTo(temp2) < 0)) {
                a[l5++] = temp3;
            }
        }
        while (l1 < r1 && l3 < r3 && l4 < r4) {
            T temp;
            T temp2;
            T temp3;
            temp = (b[l1].compareTo(d[l3]) < 0) ? b[l1++] : d[l3++];
            temp2 = (d[l3].compareTo(e[l4]) < 0) ? d[l3++] : e[l4++];
            temp3 = (b[l1].compareTo(e[l4]) < 0) ? b[l1++] : e[l4++];
            if ((temp.compareTo(temp2) < 0) && (temp.compareTo(temp3) < 0)) {
                a[l5++] = temp;
            }
            else if ((temp2.compareTo(temp3) < 0) && (temp2.compareTo(temp) < 0)) {
                a[l5++] = temp2;
            }
            else if ((temp3.compareTo(temp) < 0) && (temp3.compareTo(temp2) < 0)) {
                a[l5++] = temp3;
            }
        }
        while (l2 < r2 && l3 < r3 && l4 < r4) {
            T temp;
            T temp2;
            T temp3;
            temp = (c[l2].compareTo(d[l3]) < 0) ? c[l2++] : d[l3++];
            temp2 = (d[l3].compareTo(e[l4]) < 0) ? d[l3++] : e[l4++];
            temp3 = (c[l2].compareTo(e[l4]) < 0) ? c[l2++] : e[l4++];
            if ((temp.compareTo(temp2) < 0) && (temp.compareTo(temp3) < 0)) {
                a[l5++] = temp;
            }
            else if ((temp2.compareTo(temp3) < 0) && (temp2.compareTo(temp) < 0)) {
                a[l5++] = temp2;
            }
            else if ((temp3.compareTo(temp) < 0) && (temp3.compareTo(temp2) < 0)) {
                a[l5++] = temp3;
            }
        }
        while (l1 < r1 && l2 < r2 && l3 < r3 && l4 < r4) {
            T temp12, temp13, temp14;
            T temp23, temp24;
            T temp34;
            temp12 = (b[l1].compareTo(c[l2]) < 0) ? b[l1++] : c[l2++];
            temp13 = (b[l1].compareTo(d[l3]) < 0) ? b[l1++] : d[l3++];
            temp14 = (b[l1].compareTo(e[l4]) < 0) ? b[l1++] : e[l4++];
            temp23 = (c[l2].compareTo(d[l3]) < 0) ? c[l2++] : d[l3++];
            temp24 = (c[l2].compareTo(e[l4]) < 0) ? c[l2++] : e[l4++];
            temp34 = (d[l3].compareTo(e[l4]) < 0) ? d[l3++] : e[l4++];
            if ((temp12.compareTo(temp13) < 0) && (temp12.compareTo(temp14) < 0) && (temp12.compareTo(temp23) < 0
                    && (temp12.compareTo(temp24) < 0) && (temp12.compareTo(temp34) < 0))) {
                a[l5++] = temp12;
            }
            else if ((temp13.compareTo(temp12) < 0) && (temp13.compareTo(temp14) < 0) && (temp13.compareTo(temp23) < 0
                    && (temp13.compareTo(temp24) < 0) && (temp13.compareTo(temp34) < 0))) {
                a[l5++] = temp13;
            }
            else if ((temp14.compareTo(temp12) < 0) && (temp14.compareTo(temp13) < 0) && (temp14.compareTo(temp23) < 0
                    && (temp14.compareTo(temp24) < 0) && (temp14.compareTo(temp34) < 0))) {
                a[l5++] = temp14;
            }
            else if ((temp23.compareTo(temp13) < 0) && (temp23.compareTo(temp14) < 0) && (temp23.compareTo(temp12) < 0
                    && (temp23.compareTo(temp24) < 0) && (temp23.compareTo(temp34) < 0))) {
                a[l5++] = temp23;
            }
            else if ((temp24.compareTo(temp13) < 0) && (temp24.compareTo(temp14) < 0) && (temp24.compareTo(temp23) < 0
                    && (temp24.compareTo(temp12) < 0) && (temp24.compareTo(temp34) < 0))) {
                a[l5++] = temp24;
            }
            else if ((temp34.compareTo(temp13) < 0) && (temp34.compareTo(temp14) < 0) && (temp34.compareTo(temp23) < 0
                    && (temp34.compareTo(temp24) < 0) && (temp34.compareTo(temp12) < 0))) {
                a[l5++] = temp34;
            }

        }

        while (l1 < r1)
            a[l5++] = b[l1++];
        while (l2 < r2)
            a[l5++] = c[l2++];
        while (l3 < r3)
            a[l5++] = d[l3++];
        while (l4 < r4)
            a[l5++] = e[l4++];
    }
 
Es gab ein paar Hinweise:
1. Benenne Variablen um! Mit den Variablennamen kann man ohne viel Erfahrung das gar nicht hin kriegen!
2. Hast Du Dir den Algorithmus überlegt und durchgespielt? Ohne einen Algorithmus überlegt zu haben ist die Erfolgschance ebenfalls gleich 0!

Dein Code kann schon gar nicht funktionieren! Beim setzen der drei temp Variablen werden 3 Indeces hoch gezählt. Aber du verwendest nur eine der Zahlen! Aber der Ansatz sieht auch schon extrem zweifelhaft aus. Alleine schon die vielen while Schleifen am Anfang können so nicht richtig sein!
 
Ja, ich weiss was ich machen will aber mir fehlt die Idee für die Umsetzung. Ich will ja quasi schauen ob es in b und c und d und e noch zu kopierende Elemente gibt. Falls das der Fall ist möchte ich, je nachdem wo das kleinste Element liegt in das Array a kopieren. Ich dachte bei meinem Code, es kann ja sein dass in b c d und e noch zu kopierende Elemente sind, es kann aber auch sein dass nur in c d und e zu kopierende Elemente sind oder nur in c usw, usw... Das habe ich dann versucht zu coden
 
also ich würde mal die ganze sache einfach angehen
Java: 
public int[] merge(..Parameter für 4 arrays...)
{
    ergebnis = merge(parameter für 2)
    ergebnis2 = merge(parameter für 2)
    while...
        zusammmenbauen der ergebnisse
        
}
einfache methoden überlagerung
 
rosima26 hat gesagt.:
Ja, ich weiss was ich machen will aber mir fehlt die Idee für die Umsetzung.
Zum Vergrößern anklicken....
Die Idee wie man etwas macht gehört dazu! Das ist genau das, was Du erst ganz ohne Code machen sollst! Du sollst dir genaue Gedanken machen, wie es zu tun ist! Stell Dir vor, Du sollst jemandem erklären, wie er das zu machen hat. Das ist halt ein dumme Arbeiter - dem musst Du alles bis ins kleinste Detail erläutern.

Eine Sprache, die man nicht gut kann, eignet sich nicht, um sowas auszuarbeiten. Daher: Vergiss erst einmal Java!
 
rosima26 hat gesagt.:
Ich will ja quasi schauen ob es in b und c und d und e noch zu kopierende Elemente gibt. Falls das der Fall ist möchte ich, je nachdem wo das kleinste Element liegt in das Array a kopieren.
Zum Vergrößern anklicken....

Das ist doch schon mal ein Anfang. Es geht jetzt darum, sich diese beiden Schritte vorzunehmen und genauer zu formulieren.

Ich mach mal den ersten Schritt, formuliere aber vorher noch Deine beiden Sätze um: "so lange es in b und c und d und e noch zu kopierende Elemente gibt, kopiere das kleinste noch nicht kopierte Element in das Array a".

Mal als Skizze für einen Algorithmus
Code: 
So lange es in b und c und d und e noch zu kopierende Elemente gibt, wiederhole {
    Kopiere das kleinste noch nicht kopierte Element nach a
}

Was heißt "in b und c und d und e noch zu kopierende Elemente gibt", jetzt aber genau?

Naja, wenn l1<r1 gilt, gibt es offensichtlich noch zu kopierende Elemente. Wenn l2 < r2 gilt, auch... Also:

Code: 
So lange l1 < r1 ODER l2 < r2 ODER l3 < r3 ODER l4 < r4, wiederhole {
    Kopiere das kleinste noch nicht kopierte Element nach a
}

Wenn Du Dir das jetzt ansiehst, dann passt Dein Code überhaupt nicht zu Deinem Lösungsansatz. Bleib mal da dran und überleg Dir den - wieder viel zu allgemein formulierten - Schritt in der Schleife.
 
Ist zwar nicht mein Thread aber ich hoffe, ich kann auch eine Frage einwerfen:
Java: 
            c[l3++] = (a[l1].compareTo(b[l2]) < 0) ? a[l1++] : b[l2++];
Grundsätzlich verstehe ich die Zeile, auch den ternären Operator (oder wie das Teil heißt) das rechts benutzt wird.
Nur das sozusagen als Index tatt I3, I1, etc. die entsprechende Inkrementverison benutzt wird, verwundert miche twas.
Wie wird das ausgewertet?
Erst die Zuweisung hier gemacht und danach dann I3,I1 und I2 (wo zutreffend) um eines erhöht?

Als erst die Zuweisung und dann das inkrementieren?

Wusste nicht dass man das so in einer Zeile beides machen kann
 
berndoa hat gesagt.:
Ist zwar nicht mein Thread aber ich hoffe, ich kann auch eine Frage einwerfen:
Java: 
            c[l3++] = (a[l1].compareTo(b[l2]) < 0) ? a[l1++] : b[l2++];
Grundsätzlich verstehe ich die Zeile, auch den ternären Operator (oder wie das Teil heißt) das rechts benutzt wird.
Nur das sozusagen als Index tatt I3, I1, etc. die entsprechende Inkrementverison benutzt wird, verwundert miche twas.
Wie wird das ausgewertet?
Erst die Zuweisung hier gemacht und danach dann I3,I1 und I2 (wo zutreffend) um eines erhöht?

Als erst die Zuweisung und dann das inkrementieren?

Wusste nicht dass man das so in einer Zeile beides machen kann
Zum Vergrößern anklicken....
probier es aus 😉
ein simples beispiel ist leicht baubar
 
berndoa hat gesagt.:
Nur das sozusagen als Index tatt I3, I1, etc. die entsprechende Inkrementverison benutzt wird, verwundert miche twas.
Zum Vergrößern anklicken....
So etwas macht man normalerweise auch nicht, weils einfach scheiße zu lesen ist 🙂

berndoa hat gesagt.:
Erst die Zuweisung hier gemacht und danach dann I3,I1 und I2 (wo zutreffend) um eines erhöht?
Zum Vergrößern anklicken....
Nein. Der Postinkrement-Operator (x++) erhöht x um 1, liefert als Ergebnis den Wert vor der Erhöhung.

D. h.
Java: 
int i = 5;
System.out.println(i++);
gibt zwar 5 aus, der Wert von i beträgt nach dem Ausführen von i++ aber bereits 6.
 
mihe7 hat gesagt.:
So etwas macht man normalerweise auch nicht, weils einfach scheiße zu lesen ist 🙂


Nein. Der Postinkrement-Operator (x++) erhöht x um 1, liefert als Ergebnis den Wert vor der Erhöhung.

D. h.
Java: 
int i = 5;
System.out.println(i++);
gibt zwar 5 aus, der Wert von i beträgt nach dem Ausführen von i++ aber bereits 6.
Zum Vergrößern anklicken....
oh okay, dann wird also die zuweisung mit den alten Werten gemacht, aber trotzdem die werte erhöht.
 
Willkommen bei unserem Prof, den interessiert es auch absolut nicht ob was lesbar ist oder nicht. Danke für den Input, werde mich dem jetzt nochmal widmen
 
rosima26 hat gesagt.:
Willkommen bei unserem Prof,
Zum Vergrößern anklicken....
wir hatten einen prof der dem c compiler die schuld gegeben hat weil "gestern hat das compilieren ja noch funktioniert"... jaja diese compiler die sich immer diese späßle erlauben 😀

aber ja die main methode ändert sich in c ja täglich... da kann man halt nichts machen
 
berndoa hat gesagt.:
oh okay, dann wird also die zuweisung mit den alten Werten gemacht, aber trotzdem die werte erhöht.
Zum Vergrößern anklicken....

Genau, das Ding wertet einfach die Ausdrücke aus. Das geschieht grundsätzlich von links nach rechts, allerdings muss vor der Zuweisung selbst natürlich Ergebnis auf der rechten Seite ausgewertet werden.

Java: 
int l = 1;
a[l++] = l;
System.out.println(l);
wird also zu
Java: 
a[1] = 2;
System.out.println(2);
weil das l++ links zuerst ausgewertet wird.

Besonders "lustig", wenn der Postinkrement mehrfach auf die gleiche Variable angewendet wird:
Java: 
int l = 1;
a[l++] = l++;
System.out.println(l);
wird zu
Java: 
a[1] = 2;
System.out.pritnln(3);
 
Meinst du in diese Richtung?
Java: 
while(l1 < r1 || l2 < r2 || l3 < r3 || l4 < r4) {
            if (l1<l2 && l1<l3 && l1<l4) {
                a[l5++] = b[l1++];
            }
            else if (l2<l1 && l2<l3 && l2<l4) {
                a[l5++] = c[l2++];
            }
            else if (l3<l1 && l3<l2 && l3<l4) {
                a[l5++] = d[l3++];
            }
            else if (l4<l1 && l4<l2 && l4<l3) {
                a[l5++] = e[l4++];
            }
        }
 
Nicht ganz, so gibt das natürlich keinen Sinn: Du vergleichst nur Indizes miteinander. Du suchst aber das kleinste Element, nicht den kleinsten Index.
 
Nachtrag: Du sollst Dich auch nicht am gegebenen Code orientieren, sondern Dir eine Lösung überlegen (formulieren) und dann in Code umsetzen. Das hat Dir @KonradN schon mehrfach nahegelegt und ich habe Dir in #27 gezeigt, wie so etwas aussehen kann. Du musst das Problem, das bereits auf "Kopiere das kleinste noch nicht kopierte Element nach a" reduziert wurde, in einfachere Probleme zerlegen, die Du dann lösen kannst (s. dazu auch Kommentar #2 von @yfons123).

Das können ganz kleine Schritte hin zur Lösung sein, z. B. die Überlegung: bevor ich das Element kopieren kann, muss ich es erstmal finden. Also kannst Du schon mal zwei Schritte draus machen, die Du wieder einzeln betrachten kannst.
 
Hallo hier mal eine Variante mit deinem Code und den Zetteln von Konrad Post #10.
Bei deine Variante mit der Klasse „ T“ musst du natürlich die "compareTo" Methode sinnvoll überschreiben.

Oder Sollte das T ein Generic sein ?
Dann hätte aber „<T>“ vor der Methoden Definition stehen müssen.


Java: 
public class Merge {

    public Merge() {
        int[] s1 = {4, 9, 11};
        int[] s2 = {3, 8};
        int[] s3 = {1};
        int[] s4 = {10, 12, 14, 27};

        int[] ergebnis = merge4(s1, s2, s3, s4);
        System.out.println(Arrays.toString(ergebnis));
    }

    public static void main(String[] args) {
        new Merge();
    }

    public int[] merge4(int[] b, int[] c, int[] d, int[] e) {
        int[] a = merge(b, c);
        a = merge(a, d);
        a = merge(a, e);
        return a;
    }

   public int[] merge(int[] b, int[] c) {
        int[] a = new int[b.length + c.length];
        int la = 0;
        int lb = 0;
        int lc = 0;

        while (lb < b.length && lc < c.length) {
            if (b[lb] <= c[lc]) {
                a[la] = b[lb];
                la++;
                lb++;
            } else {
                a[la] = c[lc];
                la++;
                lc++;
            }
        }

        while (lb < b.length)
            a[la++] = b[lb++];

        while (lc < c.length)
            a[la++] = c[lc++];

        return a;
    }
}
 
Java: 
// was macht die Methode bei
String a = "1";
String b = "10";

  c[l3++] = (a[l1].compareTo(b[l2]) < 0) ? a[l1++] : b[l2++];

// ist dann "1" compareTo "10" kleiner als 0 ?
// was wird hier in c gespeichert  a ober b?
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Interaktives Merge mit Subversive
Antworten: 13
Merge ints
Antworten: 10
Struktogramm für Merge-Sort
Antworten: 1
Merge Sort
Antworten: 11
Merge-Sort als Baum darstellen
Antworten: 3

Zurück
Oben