Merge-Algorithmus

[rosima26]

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 😘

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++];

 

[yfons123]

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

und

7 8 K A

dann stöpselst du es wieder zusammen

du nimmst das kleinste immer von den stapeln
also wächst dein sortierter stapel so

7

7 8

7 8 9

7 8 9 K

gleichheit von K also einfach gleich mit

7 8 9 K K

gleiche beim Ass

7 8 9 K K A A A

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

 

[rosima26]

ja das kapiere ich aber ich kann den code nicht lesen

 

[yfons123]

dann benenne die variablen um und mach clean code daraus, so eine variablen benennung ist halt absolut beschissen... niemand kann das auf anhieb lesen

 

[mihe7]

ja das kapiere ich aber ich kann den code nicht lesen

Was heißt, Du kannst den Code nicht lesen?

Verstehst Du nicht, wie while oder && oder das ++ im []-Operator zu deuten sind oder geht es um etwas anderes?

Wo genau hast Du Schwierigkeiten?

 

[rosima26]

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...

 

[mihe7]

/** 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++];

 

[rosima26]

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

 

[mihe7]

Hast du vielleicht noch einen Tipp wie ich die erste While Schleife umschreiben könnte, dass das mit 4 anstatt 2 Arrays gemacht wird?

Ich wage zu bezweifeln, dass Du das tun sollst. Wie lautet denn die genaue Aufgabenstellung?

 

[KonradN]

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.

 

[KonradN]

Ich wage zu bezweifeln, dass Du das tun sollst. Wie lautet denn die genaue Aufgabenstellung?

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.

 

[rosima26]

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 😪

 

[Fabicode]

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 😪

Moin mein bester schick doch deinen neuen Code mal rein und sage was am neuen das Problem ist

 

[yfons123]

Bei so Aufgaben kann ich nur immer wieder empfehlen: Spiele es einmal durch!

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...

 

[mihe7]

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 😪

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.

 

[Fabicode]

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.

Stimmt kann man ja auch so machen haha

 

[mihe7]

Ich meine, dass es tatsächlich so Aufgaben gab. Statt aufteilen in 2 Bereiche dann Aufteilen in n Bereiche bei QuickSort ...

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

 

[rosima26]

Komme einfach nicht weiter was diese beschissene Merge Methode betrifft... raubt mir echt die Kraft

 

[Jw456]

Hast du denn Post #15 versucht?

 

[rosima26]

Da bin ich grade dran. Habe gestern das geschrieben, die innersten 6 Zahlen des Arrays werden aber nicht sortiert

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++];
    }

 

[rosima26]

jmd noch ne Idee vielleicht?

 

[KonradN]

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!

 

[rosima26]

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

 

[yfons123]

also ich würde mal die ganze sache einfach angehen

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

 

[KonradN]

Ja, ich weiss was ich machen will aber mir fehlt die Idee für die Umsetzung.

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!

 

[yfons123]

was Du erst ganz ohne Code machen sollst!

funktioniert auch nur bis zu einem gewissen grad..

manchmal wirft man alles während dem "tun" zusammen und machts anders

 

[mihe7]

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.

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

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:

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.

 

[berndoa]

Ist zwar nicht mein Thread aber ich hoffe, ich kann auch eine Frage einwerfen:

            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

 

[yfons123]

Ist zwar nicht mein Thread aber ich hoffe, ich kann auch eine Frage einwerfen:

            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

probier es aus
ein simples beispiel ist leicht baubar

 

[mihe7]

Nur das sozusagen als Index tatt I3, I1, etc. die entsprechende Inkrementverison benutzt wird, verwundert miche twas.

So etwas macht man normalerweise auch nicht, weils einfach scheiße zu lesen ist

Erst die Zuweisung hier gemacht und danach dann I3,I1 und I2 (wo zutreffend) um eines erhöht?

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

D. h.

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.

 

[berndoa]

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.

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.

oh okay, dann wird also die zuweisung mit den alten Werten gemacht, aber trotzdem die werte erhöht.

 

[rosima26]

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

 

[yfons123]

Willkommen bei unserem Prof,

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

 

[mihe7]

oh okay, dann wird also die zuweisung mit den alten Werten gemacht, aber trotzdem die werte erhöht.

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.

int l = 1;
a[l++] = l;
System.out.println(l);

wird also zu

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:

int l = 1;
a[l++] = l++;
System.out.println(l);

wird zu

a[1] = 2;
System.out.pritnln(3);

 

[rosima26]

Meinst du in diese Richtung?

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++];
            }
        }

 

[mihe7]

Nicht ganz, so gibt das natürlich keinen Sinn: Du vergleichst nur Indizes miteinander. Du suchst aber das kleinste Element, nicht den kleinsten Index.

 

[rosima26]

Orientiere mich am gegebenen Code, da wird das ähnlich gemacht... Bin echt überfragt langsam

 

[mihe7]

Orientiere mich am gegebenen Code, da wird das ähnlich gemacht... Bin echt überfragt langsam

Nein, Du schaust Dir nur die l und r an, nicht aber die b[l1], c[l2] usw.

 

[mihe7]

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.

 

[Jw456]

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.

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;
    }
}

 

[KonradN]

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

Wir haben ja nur die Methode gesehen. Das Generic wird bestimmt auf der Klasse angegeben worden sein.

 

[rosima26]

Genau. Ist ein Generic

 

[Jw456]

Genau. Ist ein Generic

OK und mit welchem Datentyp rufst du deine Klasse auf?

Wie schaut deine compareTo Methode aus, macht die auch bei allen möglichen Datentypen genau das was du willst?

 

[Jw456]

// 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?

 

[rosima26]

Da wird a drin gespeichert. Wenn da True ist wird das erste ausgeführt, sonst das zweite

 

[Jw456]

Wenn das so ist wo ist jetzt das Problem?

 

[rosima26]

Kriege die Methode nicht hin, das ist das Problem

 

[Jw456]

Dann schaue dir mein Beispiel an.

 

[yfons123]

Kriege die Methode nicht hin, das ist das Problem

das problem wirst du öfter haben

einen merge algorithmus in einer klausur dran zu nehmen ist unrealistisch

 

[Jw456]

Du solltest etwas mehr von deinen Code zeigen wenn du Hilfe haben willst.