mergesort Problem

Hallo,

fülle ein Array mit Pseudozufallszahlen und übergebe es der funktion mergesort. In der Ausgabe bekommt ich irgendwelche zahlen. Diese zahlen sind weder sortiert noch die erzeugten.

int merge(int *F1, int *F2, int n){
	int F[n*2];
	int i,k,j,t;
	i=0;
	j=0;
	k=0;
	t=0;
	/*Liste leer?*/
	while(i<n && j<n){
		if(F1[i] < F2[j]){
			t=F1[i];
			i++;	
		}else{
			t=F2[j];
			j++;			
		}	
		F[k]=t;
		k++;
	}
	/*Rest anhängen*/
	while(i<n){
		F[k]=F1[i];
		k++;i++;			
	}
	while(j<n){
		F[k]=F2[j];
		k++;j++;			
	}
	return *F;	
}

int mergesort(int *F, int n){
	int i,j,k;
	j=0;
	k=0;
	int F1[n/2];
	int F2[n/2]; 
	/*Divide*/
	if(n>1){
		for(i=0;i<n;i++){
			if(i<n/2){
				F1[j]=F[i];
				j++;	
			}else{
				F2[k]=F[i];
				k++;
			}	
		}
		/*Conquer*/
		mergesort(F1,j);
		mergesort(F2,k);
		/*Combine*/
		return merge(F1, F2,n/2);
	}
	return *F;
}

CStoll

Du mergest die beiden Felder in ein lokales Array (das am Ende der Funktion merge() wieder zerstört wird) und gibst dann das erste Element dieses Arrays wieder zurück. So kann das nicht funktionieren.

kannst du mir da weiterhelfen?

MFK

Du musst das Zielarray als Parameter an merge übergeben. Außerdem kannst du dich nicht darauf verlassen, dass F1 und F2 gleich groß sind. Eine Größenangabe für beide reicht also nicht.

warum muss ich ein zielarray übergegen? müsste doch das array der funktion zurückbekommen.
wie kann ich es sonst machen außer mit der länge? kann man abfragen ob array == leer ist?

MFK

booorgy schrieb:

warum muss ich ein zielarray übergegen?

Weil du kein Array zurückgeben kannst.

wie kann ich es sonst machen außer mit der länge? kann man abfragen ob array == leer ist?

Nein. Übergib doch einfach zwei ints.

Dravere

Zudem hat deine Lösung auch noch das Problem, dass es ungrade Zahlen abschneidet. Wenn 7 übergeben wird, werden nur 6 davon behandelt. Das ist wegen dem zweimal n/2 ergibt bei 7 zweimal 3 also 6.

Und so geht es wirklich:

void Merge(int* LeftArray, int* RightArray, int* ResultArray, int nLeft, int nRight)
{
    int nL = 0, nR = 0, nResult = 0;
    while(nL < nLeft && nR < nRight)
    {
        if(LeftArray[nL] > RightArray[nR])
        {
            ResultArray[nResult] = RightArray[nR];
            nR++; nResult++;
        }
        else
        {
            ResultArray[nResult] = LeftArray[nL];
            nL++; nResult++;
        }
    }
    while(nL < nLeft)
    {
        ResultArray[nResult] = LeftArray[nL];
        nL++; nResult++;
    }
    while(nR < nRight)
    {
        ResultArray[nResult] = RightArray[nR];
        nR++; nResult++;
    }
}

void MergeSort(int* Array, int nCount)
{
    if (nCount > 1)
    {
        int nLeftCount = (nCount / 2);
        int nRightCount = (nCount - nLeftCount);
        int LeftArray[nLeftCount];
        int RightArray[nRightCount];

        for(int i = 0; i < nLeftCount; i++)
        { LeftArray[i] = Array[i]; }

        for(int i = 0; i <nRightCount; i++)
        { RightArray[i] = pArray[i + nLeftCount]; }

        MergeSort(LeftArray, nLeftCount);
        MergeSort(RightArray, nRightCount);
        Merge(LeftArray, RightArray, Array, nLeftCount, nRightCount);
    }
}

Code ist nur hier reingeschrieben. Ich gebe keine Garantie, dass es keine Fehler drin hat. Aber in der Art sollte es eigentlich gehen.

Grüssli