Was passiert in dieser Methode?

[bob651]

HI, ich implementiere imMo einen Mergesort und habe jetzt die Methode mischen:

 private void mischen(int links, int mitte, int rechts) {
//methode mischt alle arrays
        for (int i = links; i <= rechts; i++) {    //solange rechts größer/gleich links -->links erhöhen
            zsmfugen[i] = array[i];
        }
      
        int i = links;
        int j = mitte + 1;
        int k = links;
     
      
        while (i <= mitte && j <= rechts) {
            if (zsmfugen[i] <= zsmfugen[j]) {
                array[k] = zsmfugen[i];
                i++;
            } else {
                array[k] = zsmfugen[j];
                j++;
            }
            k++;
        }
        while (i <= mitte) {
            array[k] = zsmfugen[i];
            k++;
            i++; }}

Also könntet ihr mir sagen, was genau gemacht wird? Also z.B warum ist int i und k beide =links ?
Und was soll die while Schleife bringen?
Ich habe es so verstanden, dass
"Solange i <= Mitte ist und rechts <= mitte"
"Wenn usmfugen <= zsmfugen[j] ist, soll der wert von array[k] in zsmfugen gespeichert werden"
"dann soll i erhöht werden"

Aber warum wird i erhöht. Blicke nicht so ganz durch.
Wäre cool wenn ihr mir paar Tipps geben könntet.

 

[Meniskusschaden]

Also z.B warum ist int i und k beide =links ?

i durchläuft das Array von der ersten Position bis zur Mitte, j durchläuft es von der Mitte bis zum Ende und k von der ersten bis zur letzten Position.

Und was soll die while Schleife bringen?

Welche der beiden? Die erste wird durchlaufen, solange noch keine der beiden Array-Hälften vollständig durchlaufen wurde.
Danach wird mit der zweite while-Schleife noch der Rest der ersten Array-Hälfte durchlaufen. Da müsste sicher noch eine dritte Schleife folgen, um den Rest der zweiten Array-Hälfte zu verarbeiten.

Am besten machst du mal einen Schreibtischtest. Dann sieht man ganz gut, was da vor sich geht.

 

[bob651]

Hm, also verstehe noch nicht was die while schleife bringt. Also wann sie durchläuft weiß ich, aber nicht was sie macht. z.B
array[k}= zsmfugen[i);
i++:
was genau macht es?
Ich hab in der Theorie verstanden, wie der Algorithmus geht, also durch 2 teilen, zsmfügen usw.

also ich habe ja 2 int arrays (array, zsmfugen), dann habe ich noch einen inputarray

private int[] array;
    private int[] zsmfugen;
    private int lange;

public void zerlegen(int inputArray[]) {
        this.array = inputArray;
        this.lange = inputArray.length;
        this.zsmfugen = new int[lange];
        mergesort(0, lange - 1);
    }

bringt mich alles iwie durcheinander, hoffe kannst mir da noch weiterhelfen

 

[Meniskusschaden]

Hm, also verstehe noch nicht was die while schleife bringt. Also wann sie durchläuft weiß ich, aber nicht was sie macht. z.B
array[k}= zsmfugen[i);
i++:
was genau macht es?

Du kannst dir i, j und k als Zeiger auf drei Mengen vorstellen: die beiden bereits in sich sortierten Teilarrays (links bis mitte und mitte+1 bis rechts) und das noch nicht sortierte Gesamtarray.
In der ersten Schleife läufst du mit den Zeigern i und j so durch die beiden Teilarrays, dass du jeweils das kleinere der beiden Elemente auf die i und j zeigen an die Position k des Gesamtarrays kopierst. Nach dem Kopieren eines Elementes werden k und entweder i oder j um 1 erhöht und die nächste Schleifeniteration beginnt.
Irgendwann wurde entweder das erste oder das zweite Teilarray vollständig in das Gesamtarray kopiert. Das ist der Zeitpunkt, an dem die erste Schleife endet. Dann sind aber noch in paar Elemente in dem anderen Teilarray übrig.
Angenommen das zweite Teilarray wurde komplett kopiert (j). Dann zeigt i noch auf die erste Position des ersten Teilarrays, die noch nicht kopiert wurde und k auf die nächste freie Position des Gesamtarrays. Die zweite Schleife kopiert diese Elemente nun in das Gesamtarray und muß deshalb natürlich in jeder Iteration i und k erhöhen, damit jeweils das nächste Element des ersten Teilarrays in die nächste Position des Gesamtarrays kopiert wird.
Für den Fall, dass in der ersten Schleife das erste Teilarray komplett verarbeitet wurde, muß man das analog auch für das zweite Teilarray realisieren.