MergeSort

freakC++

Hallo zusammen,
ich interessiere mich für den MergeSort. Das Prinzip (Divide-and-Conquer) habe ich verstanden, doch suche ich nun Beispielcode, da ich keine Zeit habe, das jetzt selbst zu programmieren (erst wieder in den Ferien). Den habe ich auf gefunden, doch ist der Code viel zu komplex, als dass ich ihn wie beispielsweise beim BubbleSort einfach so verstehe.

Kennt jemand eine einfache Variante dieses Algorithmus oder ein gutes Tutorial, das mit Code arbeitet? Ich will den Code verstehen, das Prinzip ist mir bekannt.

Ich hätte diesen Code hier, der auch funktioniert:

void Merge(int* ipA, int iEnd1, int iEnd2) {
    int i = 0;
    int j = iEnd1;
    int k = 0;
    int* ipTemp = new int[iEnd2];
    // Take each next smallest element
    while (i < iEnd1 && j < iEnd2) {
        if (ipA[i] < ipA[j]) {
            ipTemp[k] = ipA[i];
            ++i;
        } else {
            ipTemp[k] = ipA[j];
            ++j;
        }
        ++k;
    }
    // Copy any remaining elements of the 1st array
    while (i < iEnd1) {
        ipTemp[k] = ipA[i];
        ++i;
        ++k;
    }
    // Copy any remaining elements of the 2nd array
    while (j < iEnd2) {
        ipTemp[k] = ipA[j];
        ++j;
        ++k;
    }
    // Copy the merged array back to the original
    for (int iIndex = 0; iIndex < iEnd2; ++iIndex) {
        ipA[iIndex] = ipTemp[iIndex];
    }
    delete [] ipTemp;
}

int main() {
    using namespace std;

    int iaArray[] = {24, 5, 3, 35, 14, 23, 19};
    int iSize = 7;

    // Merge Sort
    for (int i = 1; i < iSize; i *= 2) {
        for (int j = 0; j < iSize - i; j += 2*i) {
            int iEnd2 = (2*i < iSize - j) ? 2*i : iSize - j;
            Merge(&(iaArray[j]), i, iEnd2);
        }
    }

    // Output sorted array
    for (int i = 0; i < iSize; i++){
        cout << iaArray[i] << "  ";
    }
    cout << endl;

    return 0;
}

Mit dem ersten Parameter wird das zu sortierende Array übergeben und wofür stehen die beiden anderen? Außerdem frage ich mich, wo das Rekursive zu finden ist.

Vielen Dank
lg, freakC++

freakC++ schrieb:

Mit dem ersten Parameter wird das zu sortierende Array übergeben und wofür stehen die beiden anderen? Außerdem frage ich mich, wo das Rekursive zu finden ist.

Linke und rechte Grenze des zu sortierenden Teilarrays vermutlich.
Sieht außerdem eher nach dem natürlichen MergeSort aus als nach dem klassischen.

freakC++

Mmmh...danke schonmal! Was ist der Unterschied zwischen dem Klassischen und dem Natürlichen? Liege ich denn richtig, dass hier nicht rekursiv gearbeitet wird. Das ist mir nämlich sehr wichtig!

Vielen Dank
lg, freakC++

volkard

nms schrieb:

freakC++ schrieb:

Mit dem ersten Parameter wird das zu sortierende Array übergeben und wofür stehen die beiden anderen? Außerdem frage ich mich, wo das Rekursive zu finden ist.

Linke und rechte Grenze des zu sortierenden Teilarrays vermutlich.
Sieht außerdem eher nach dem natürlichen MergeSort aus als nach dem klassischen.

Nö.
Natürliches Mergesort sehe ich da nicht. Die Rekursion wurde weggefrickelt, um ... Keine Ahnung, warum.

freakC++

Hat denn jemand einen rekursiven Code? Ich finde irgendwie keinen und es ist mir wichtig.

Außerdem: Der oben gezeigte Code funktioniert dann aber doch nach dem "Divide-and-Conquer Prinzip"? Weil dieses Prinzip ja eigentlich auf der Rekursion beruht.

Vielen Dank
lg, freakC++

volkard

//ungetestet
void Merge(int* ipA, int iEnd1, int iEnd2) {

    if(iEnd2-iEnd1<=1) 
       return;
    int iMitte=(iEnd1+iEnd2)/2;
    Merge(ipA,iEnd1,iMitte);
    Merge(ipA,iMitte,iEnd1);

    int i = 0;
    int j = iEnd1;
    int k = 0;
    int* ipTemp = new int[iEnd2];
    // Take each next smallest element
    while (i < iEnd1 && j < iEnd2) {
        if (ipA[i] < ipA[j]) {
            ipTemp[k] = ipA[i];
            ++i;
        } else {
            ipTemp[k] = ipA[j];
            ++j;
        }
        ++k;
    }
    // Copy any remaining elements of the 1st array
    while (i < iEnd1) {
        ipTemp[k] = ipA[i];
        ++i;
        ++k;
    }
    // Copy any remaining elements of the 2nd array
    while (j < iEnd2) {
        ipTemp[k] = ipA[j];
        ++j;
        ++k;
    }
    // Copy the merged array back to the original
    for (int iIndex = 0; iIndex < iEnd2; ++iIndex) {
        ipA[iIndex] = ipTemp[iIndex];
    }
    delete [] ipTemp;
}

int main() {
    using namespace std;

    int iaArray[] = {24, 5, 3, 35, 14, 23, 19};
    int iSize = 7;

    // Merge Sort
    Merge(iArray,0,7);

    // Output sorted array
    for (int i = 0; i < iSize; i++){
        cout << iaArray[i] << "  ";
    }
    cout << endl;

    return 0;
}

freakC++

Hey,
das ist sehr nett, dass du mir so schnell Hilfe bietest. Zwar ist der Code (bis auf ein a) syntaktisch korrekt, doch das Sortieren funktioniert nicht. Es wird nämlich gar nicht sortiert. Auch finde ich auf die Schnelle den Fehler nicht (ich habe die Vermutung, dass nur eine Kopie des Array sortiert wird, aber ich weiß nicht, ob das stimmt). Siehst Du eventuell den Fehler oder hast Du einen anderen einfachen, rekursiven MergeCode?

Vielen Dank
lg, freakC++

volkard

Hab mal meine Namen benutzt, der Testfall klappt. Aber ich glaube nicht, daß das richtig ist. Ist wohl eer Zufall.

#include <iostream>
using namespace std;

//ungetestet
void Merge(int* ipA, int iBegin, int iEnd) {
    if(iEnd-iBegin<=1)
       return;
    int iMitte=(iBegin+iEnd)/2;
    Merge(ipA,iBegin,iMitte);
    Merge(ipA,iMitte,iEnd);

    int i = iBegin;
    int j = iMitte;
    int k = 0;
    int* ipTemp = new int[iEnd-iBegin];
    // Take each next smallest element
    while (i < iMitte && j < iEnd) {
        if (ipA[i] < ipA[j]) {
            ipTemp[k] = ipA[i];
            ++i;
        } else {
            ipTemp[k] = ipA[j];
            ++j;
        }
        ++k;
    }
    // Copy any remaining elements of the 1st array
    while (i < iMitte) {
        ipTemp[k] = ipA[i];
        ++i;
        ++k;
    }
    // Copy any remaining elements of the 2nd array
    while (j < iEnd) {
        ipTemp[k] = ipA[j];
        ++j;
        ++k;
    }
    // Copy the merged array back to the original
    for (int iIndex = 0; iIndex < iEnd-iBegin; ++iIndex) {
        ipA[iIndex+iBegin] = ipTemp[iIndex];
    }
    delete [] ipTemp;
}

int main() {
    using namespace std;

    int iaArray[] = {24, 5, 3, 35, 14, 23, 19};
    int iSize = 7;

    // Merge Sort
    Merge(iaArray,0,7);

    // Output sorted array
    for (int i = 0; i < iSize; i++){
        cout << iaArray[i] << "  ";
    }
    cout << endl;
}

Aber schreib Dir doch ein eigenes. Wie es funktionieren könnte, steht ja in Wikipedia. Und genügend Tricks für den Code sind hier.

freakC++

Hallo,
na klar schreibe ich mir ein eigenes. Mein Problem ist momentan der Schulstress. Daher möchte ich erst eine Beispielimplemetierung verstehen und danach - also in den Ferien wahrscheinlich - setze ich mich hin und schreibe meinen eigenen Algorithmus.
Dein Code funktioniert soweit und dafür bin ich sehr dankbar. Nun versuche ich ihn nachzuvollziehen und da brauche ich nochmals eure Hilfe.

Als Parameter wird zuerst das zu sortierende Array, dann der Sortieranfang und dann das Sortierende übergeben. Anschließend wird überprüft, ob das Array mehr als ein Element hat und gegenenfalls abgebrochen.

1.) Ich suche hier jetzt die Schritte divide, conquer und combine. Ich habe mir in Wikipedia & Co. schon einiges darüber durchgelesen und es wurde oftmals mit dem ähnlichen Schaubild erklärt, dass ein großes Array, sagen wir mit 5 Arrays, in Unterarrays, also hier 5 Arrays zerlegt wird. So habe ich das verstanden. Ich denke, dass dieser Schritt (divide) mit dem rekursiven Aufruf geschicht, doch verstehe ich nicht ganz, wo die 5 Arrays sind??

2.)Ich habe mir so eingie Gedanken über die Rekursion gemacht, doch habe ich noch einen Gedankenwurm. Wenn die Funktion zum Selbstaufruf kommt (5. Zeile), dann führt sie ja immer nur den Programmteil aus, der bis zum nächsten Selbstaufruf erfolgt. Wann wird die Restfunktion aufgerufen und wie oft?

3.) Bei dieser Zeile:

if (ipA[i] < ipA[j])

Da wird doch das Ausgangsarray verglichen und keine zerlegten Arrays. Das sieht nicht so nach MergeSort aus. Was mache ich falsch?
Vielen Dank für eure Hilfe
lg, freakC++

volkard

Habe Rekursionsaufrufverfolgungsdebugausgaben eingebaut.

#include <iostream>
using namespace std;

//ungetestet
void Merge(int* ipA, int iBegin, int iEnd, int tiefe) {
		cout<<"                       Sortiere Array von "+23-tiefe<<iBegin<<" bis "<<iEnd<<'\n';
    if(iEnd-iBegin<=1)
       return;
    int iMitte=(iBegin+iEnd)/2;
    Merge(ipA,iBegin,iMitte,tiefe+1);
    Merge(ipA,iMitte,iEnd,tiefe+1);

    int i = iBegin;
    int j = iMitte;
    int k = 0;
    int* ipTemp = new int[iEnd-iBegin];
    // Take each next smallest element
    while (i < iMitte && j < iEnd) {
        if (ipA[i] < ipA[j]) {
            ipTemp[k] = ipA[i];
            ++i;
        } else {
            ipTemp[k] = ipA[j];
            ++j;
        }
        ++k;
    }
    // Copy any remaining elements of the 1st array
    while (i < iMitte) {
        ipTemp[k] = ipA[i];
        ++i;
        ++k;
    }
    // Copy any remaining elements of the 2nd array
    while (j < iEnd) {
        ipTemp[k] = ipA[j];
        ++j;
        ++k;
    }
    // Copy the merged array back to the original
    for (int iIndex = 0; iIndex < iEnd-iBegin; ++iIndex) {
        ipA[iIndex+iBegin] = ipTemp[iIndex];
    }
    delete [] ipTemp;
}

int main() {
    using namespace std;

    int iaArray[] = {24, 5, 3, 35, 14, 23, 19};
    int iSize = 7;

    // Merge Sort
    Merge(iaArray,0,7,0);

    // Output sorted array
    for (int i = 0; i < iSize; i++){
        cout << iaArray[i] << "  ";
    }
    cout << endl;
}

Ausgabe:

Sortiere Array von 0 bis 7
 Sortiere Array von 0 bis 3
  Sortiere Array von 0 bis 1
  Sortiere Array von 1 bis 3
   Sortiere Array von 1 bis 2
   Sortiere Array von 2 bis 3
 Sortiere Array von 3 bis 7
  Sortiere Array von 3 bis 5
   Sortiere Array von 3 bis 4
   Sortiere Array von 4 bis 5
  Sortiere Array von 5 bis 7
   Sortiere Array von 5 bis 6
   Sortiere Array von 6 bis 7

freakC++

Hallo zusammen,
vielen Dank für dein Bemühen. Ich finde das echt richtig toll. Trotzdem bin ich leider noch nicht hinter alle meine Probleme gekommen.

1.) Sind die Einschübe bei der Ausgabe Absicht? Sollen das die Unterarrays sein?

2.) Ich verstehe nicht, warum immer das Ausgangsarray ipA verglichen wird. Es muss doch aufgeteilt werden und dann müssten ganz viele Arrays vorhanden sein. So wie hier:

http://de.wikipedia.org/w/index.php?title=Datei:Mergesort_example.png&filetimestamp=20050709140110

3.) Zur Rekursion: Wenn die Programmausführung zum Selbstaufruf kommt, dann wird doch eigentlich die Restfunktion nicht mehr ausgeführt, weil sie wieder von vorne beginnt. Wie ist das hier?

Mein Hauptproblem ist, dass ich das Prinzip des MergeSort nocht nicht wieder erkenne. Ich denke, dass der wichtigste Teil wohl das hier ist:

while (i < iMitte && j < iEnd) {
        if (ipA[i] < ipA[j]) {
            ipTemp[k] = ipA[i];
            ++i;
        } else {
            ipTemp[k] = ipA[j];
            ++j;
        }
        ++k;
    }

Bitte helft mir weiter. Ich gebe mir alle Mühe, alles so bald wie möglich zu vertehen!

Danke!
lg, freakC++

[edit] Ja, die Einschübe der Ausgabe sind extra. Ich habe mir das alles nochmal aufgedröselt. Das verstehe ich nun, doch wo und wie geschieht die eigentliche Aufteilung des Arrays und wo werden die Unterarrays gespeichert?

volkard

freakC++ schrieb:

1.) Sind die Einschübe bei der Ausgabe Absicht?

Ja.

[quote="freakC++"]Sollen das die Unterarrays sein?[/cpp]
Ja. Aber die Unterarrays sind keine eigenen Arrays, sondern nur Teilausschitte des Hauparrays.

Er ruft auf
Sortiere Array von 0 bis 7 
 Um das zu schaffen, macht er
 Sortiere Array von 0 bis 3 
 und
 Sortiere Array von 3 bis 7 

  um Sortiere Array von 0 bis 3 zu schaffen, macht er 
  Sortiere Array von 0 bis 1 
  und
  Sortiere Array von 1 bis 3

usw.

2.) Ich verstehe nicht, warum immer das Ausgangsarray ipA verglichen wird. Es muss doch aufgeteilt werden und dann müssten ganz viele Arrays vorhanden sein. So wie hier:
http://de.wikipedia.org/w/index.php?title=Datei:Mergesort_example.png&filetimestamp=20050709140110

Das Aufteilen und mischen geschieht nur virtuell:
für sort(anexample) ruft er zuerst sort(anex) und sort(ample) auf.
raus kommt jeweils aenx und aelmp. Weil das auf dem Ursprungsarray passiert ist, geschah um genau zu sein folgendes:
die main ruft sort(anexample,0,9) auf.
sort(anexample,0,9) ruft sort(anexample,0,4) auf, das macht aus anexample nun aenxample. Dann ruft sort(anexample,0,9) sort(aenxample,4,9) auf. das macht aus aenxample nun aenxaelmp und dann wird gemerged.
(um genau zu sein: sort(anexample,0,4) sortiert nicht einfach per zauberhand die ersten 4 zeichen, sondern per rekursion mit sort(anexample,0,2) und sort(anexample,2,4) und dann merge, jedes sort ist nur sortUnterarrays und dann merge. außer wenn ein Array so klein ist, daß es von selber schon sortiert ist.)

3.) Zur Rekursion: Wenn die Programmausführung zum Selbstaufruf kommt, dann wird doch eigentlich die Restfunktion nicht mehr ausgeführt, weil sie wieder von vorne beginnt. Wie ist das hier?

Hier beginnt nichts so von vorne, wie bei fakultät zum beispiel.

Mein Hauptproblem ist, dass ich das Prinzip des MergeSort nocht nicht wieder erkenne. Ich denke, dass der wichtigste Teil wohl das hier ist:
while (i < iMitte && j < iEnd) {
        if (ipA[i] < ipA[j]) {
            ipTemp[k] = ipA[i];
            ++i;
        } else {
            ipTemp[k] = ipA[j];
            ++j;
        }
        ++k;
    }

Das ist das mergen.
Im Array stehe mal aenxaelmp, womit eigentlich aenx|aelmp gemeint ist. Nun nimmt er immer den kleinsten und stopft ihn ins Ziel-Array.
aenx|aelmp -> _________
*enx|aelmp -> a________
*enx|*elmp -> aa_______
**nx|*elmp -> aae______
**nx|**lmp -> aaee_____
**nx|***mp -> aaeel____
**nx|****p -> aaeelm___
***x|****p -> aaeelmn__
***x|***** -> aaeelmnp_
So, ein Array ist leer. Der Rest vom alten, also hier nur x wird einfach reinkopier.
****|***** -> aaeelmnpx
Und zum Schluß wird das gemergte Array zurückkopiert.
********* -> aaeelmnpx
aaeelmnpx <- *********

freakC++

Hallo,
das hat schonmal sehr geholfen. Hierzu habe ich noch eine Frage:

Also:

Ich stelle mir das immer so vor, als wenn ich 8 Karten habe. Nun suche ich die Mitte und habe dann 2*4 karten. dann suche ich mir wieder die Mitte und habe dann 4*2 karten. Zum Schluss suche ich mir wieder die Mitte und habe 8*1 Karten. Dieses Prinzip kann hier in deinem Beispiel noch nicht so ganz wiederekennen.Beim ersten Schritt wird geteilt --> ok! Doch dann wird schon ein A rausgenommen? Was steht denn dan in diesem Array? Nicht initialisiert? Warum wird schon sortiert, obwohl das Array noch gar nicht ganz zerteil worden ist?

Vielen Dank
lg, freakC++

freakC++

Noch eine andere Frage: In der zweiten while schleife wird k als Elementzähler von temp genutzt. Ist denn k überhaupt 0, wenn angefangen wird. In der ersten while Schleife wird es nämlich inkrementiert.

Vielen Dank
lg, freakC++

freakC++

Vergesst meine zweite Frage. Die war dumm. Doch auf die davor benötige ich noch eine Antwort .

Vielen Dank
lg, freakC++

freakC++

Hallo,
ich habe noch eine andere Frage. Die anderen Postigns müsst ihr euch nicht durchlesen. Ich poste nochmal den Quelltext:

include <iostream> 
using namespace std; 

//ungetestet 
void Merge(int* ipA, int iBegin, int iEnd, int tiefe) { 
        cout<<"                       Sortiere Array von "+23-tiefe<<iBegin<<" bis "<<iEnd<<'\n'; 
    if(iEnd-iBegin<=1) 
       return; 
    int iMitte=(iBegin+iEnd)/2; 
    Merge(ipA,iBegin,iMitte,tiefe+1); 
    Merge(ipA,iMitte,iEnd,tiefe+1);  //Muss hier nicht iMitte+1 stehen?

    int i = iBegin; 
    int j = iMitte; 
    int k = 0; 
    int* ipTemp = new int[iEnd-iBegin]; 
    // Take each next smallest element 
    while (i < iMitte && j < iEnd) { 
        if (ipA[i] < ipA[j]) { 
            ipTemp[k] = ipA[i]; 
            ++i; 
        } else { 
            ipTemp[k] = ipA[j]; 
            ++j; 
        } 
        ++k; 
    } 
    // Copy any remaining elements of the 1st array 
    while (i < iMitte) { 
        ipTemp[k] = ipA[i]; 
        ++i; 
        ++k; 
    } 
    // Copy any remaining elements of the 2nd array 
    while (j < iEnd) { 
        ipTemp[k] = ipA[j]; 
        ++j; 
        ++k; 
    } 
    // Copy the merged array back to the original 
    for (int iIndex = 0; iIndex < iEnd-iBegin; ++iIndex) { 
        ipA[iIndex+iBegin] = ipTemp[iIndex]; 
    } 
    delete [] ipTemp; 
}

Muss da oben nicht iMitte+1 stehen? Sonst wird immer ein Element doppelt bearbeitet.

Vielen Dank
lg, freakC++

volkard

freakC++ schrieb:

Muss da oben nicht iMitte+1 stehen? Sonst wird immer ein Element doppelt bearbeitet.

Ich hatte festgelegt, daß Begin aus erste Element im Array zeigt udn End aufs erste Element HINTER dem Array, also außerhalb.

freakC++

Hallo volkard,
sorry...aber ich verstehe deine Antwort nicht so ganz . Mir wird nicht klar, warum das Elemt in der Mitte dann nicht doppelt genommen wird. Liegt das mit an meiner Abbruchbedinung? Mir ist schon klar, dass das Begin auf das erste Element des "Linken" Arrays und End auf das erste Element des "rechten" Arrys zeigt.

Kannst Du mir das nochmal anders klar machen? Vielen Dank dafür!

lg, freakC++