Anhang: testmergesort.exe (173, KB)Also hier einmal eine lauffähige C Version des Programmes. Wie man sieht, habe ich lediglich ein paar Spielereien eingebaut. Z.B., dass das Hilfsarray dynamisch abhängig vom übergebenen Wert angelegt wird.
Dann meldet sich jede Instanz von mergesort, sagt der wievielte Aufruf er ist, in welcher Rekursionsebene er sich gerade befindet und welchen String er sortieren soll. (Und ja, ich weiß, dass man da noch viel optimieren kann. Bin etwas eingerostet in C... Wollte aber zeigen, dass es so funzt.
Das lauffähige Programm habe ich auch mal angefügt. Es erwartet als Parameter den zu sortierenden String. Für unser Beispiel wird es also mit "testmergesort caroline" aufgerufen.
Hier die Source:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int iRekEbene = 0;
int iAnzAufruf = 0;
void mergesort( char *, char *, int, int );
int main(int argc, char *argv[])
{
int iAnzElemente = 0;
int z;
if (argc > 1)
{
printf( "zu sortierender String: %s\n", argv[1] );
for (z=0;argv[1][z]>0;z++) iAnzElemente++;
printf( "Anzahl Elemente : %d\n\n", iAnzElemente );
char b[ iAnzElemente ]; // Hilfarray anlegen mit gleicher Größe
mergesort( argv[1], &b[0], 0, iAnzElemente - 1 );
printf( "\nsortierter String : %s\n\n", argv[1] );
}
return 0;
}
void mergesort( char a[], char b[], int l, int r ) // l=linker Rand, r=rechter Rand
{
int iCount;
iAnzAufruf++; // der wievielte Aufruf von Mergesort ist das?
iRekEbene++; // welche Rekursionsebene?
printf( "%3d. Aufruf, %3d. Ebene, sortiere den String: ", iAnzAufruf, iRekEbene);
for(iCount=l; iCount <= r ; iCount++) printf("%c",a[iCount]);
printf("\n");
if(r>l) // ist es mehr als ein Element?
{
int i, j, k, m; // Variablen deklarieren
m=(r+l)/2; // Mitte ermitteln
mergesort(a, b, l, m); // linke Teildatei rekursiv sortieren lassen
mergesort(a, b, m+1, r); // rechte " " " "
for(i=m+1; i>l; i--) b[i-1]=a[i-1]; // linke Teildatei in Hilfsarray
for(j=m; j<r; j++) b[r+m-j]=a[j+1]; // rechte Teildatei umgedreht in Hilfsarray
for(k=l; k<=r; k++)
a[k]=(b[ i ] < b[ j ] ) ? b[ i++ ]:b[ j-- ]; // füge sortiert in a ein
}
iRekEbene--;
}
Lufton schrieb:Ich biete "caroline", 0, 7... (aber um 04:27 will ich das verzeihen )
OpenEyes schrieb:Das Problem hier ist, dass der zweite Aufruf nicht erreicht wird solange r > l,
kisa schrieb am 19.04.2010:void mergesort(int a[], int l, int r){ // l=linker Rand, r=rechter Rand
interpreter schrieb:1 Instanz aufgerufen mit 0 und 7
