Alle guten Dinge sind drei: MergeSort

Max3000

/edit pumu: Beleidigungen gelöscht.

Bei ++index fängt der in dem temporären Feld bei 1 an zu zählen.
Das Feld ist aber von 0 an gefüllt. Da gibts auch nix zu lachen weil irgendwie scheinst du keine Ahnung zu haben.

MFK

Max3000 schrieb:

Bin mir nicht sicher, aber das ++iIndex in der letzten for-Schleife, müsste das nicht iIndex++ heissen?

Das ist an dieser Stelle völlig egal. Das unterscheidet sich ausschließlich im Rückgabewert des Ausdrucks, und der wird hier nicht verwendet.

Max3000 schrieb:

Bei ++index fängt der in dem temporären Feld bei 1 an zu zählen.

Au weia.

Das Problem ist die Mitte-Berechnung. Wenn der iEnd-Parameter für "Eins dahinter" stehen soll, muss der iEnd-Parameter des ersten rekursiven Aufrufs gleich dem iBegin-Parameter des zweiten Aufrufs sein, sonst fehlt da was.

Am besten wirfst du das ganze +1 raus und machst aus den <= einfach <, dann passt's.

Max3000

Warum muss es in diesem Forum eigentlich solche Deppen geben, die unangemeldet irgendeinen Mist posten?

Und tut mir ja leid falls ich mich geirrt habe.
Dachte bei ++i wird i am Ende der Schleife erhöht.

Darf man sich nicht mal irren?

freakC++

Hallo zusammen,
also ursprünglich war das auch ohne "+1" doch möchte ich dieses eigentlich beibehalten, da es dann verständlicher ist. Wenn bei "iMitte" aufgehört wird und bei "iMitte" angefangen wird, kann das erstmal zur Verwirrung führen. Ich höre also mit der Mitte auf und fange dahinter wieder an. Deswegen wollte ich das umschreiben, doch es funktioniert nicht.

Was muss ich noch ändern, weil ich eigentlich dachte, dass ich alle "Größer-Kleiner-Zeichen" bereits angeglichen habe?

Vielen Dank :xmas2:
lg, freakC++

pumuckl

Max3000 schrieb:

Warum muss es in diesem Forum eigentlich solche Deppen geben, die unangemeldet irgendeinen Mist posten?

Einfach nicht drauf eingehen ist die beste Reaktion. Mit Beleidigungen und Beschimpfungen zu reagieren die denkbar schlechteste, damit fütterst du die Trolle nicht nur, sondern begibst dich zusätzlich auch noch auf ihr Niveau. Bitte unterlass derartige Äußerungen in Zukunft.

freakC++

Kinderlein, ich beende hiermit den Streit. Ich brauch eher Antworten KÖnnt ihr mir helfen?

Vielen Dank
lg, freakC++

MFK

freakC++ schrieb:

also ursprünglich war das auch ohne "+1" doch möchte ich dieses eigentlich beibehalten, da es dann verständlicher ist.

Es ist dann aber falsch.

freakC++ schrieb:

Wenn bei "iMitte" aufgehört wird und bei "iMitte" angefangen wird, kann das erstmal zur Verwirrung führen.

Sollte es nicht. Alle Algorithmen, die auf Sequenzen arbeiten, erwarten einen Iterator auf das Startelement sowie einen Iterator hinter (nicht auf) das Endelement. Und genau so wird der iEnd-Parameter ja auch behandelt. Du sortierst bis < iEnd, nicht <=.

freakC++ schrieb:

Ich höre also mit der Mitte auf und fange dahinter wieder an.

Nein, du hörst eins vor der Mitte auf und fängst hinter der Mitte wieder an. Du lässt also das Element an der Mitte-Position aus.

freakC++ schrieb:

Deswegen wollte ich das umschreiben, doch es funktioniert nicht.

Du kannst deine Sortierfunktion natürlich so umschreiben, dass sie semantisch anders arbeitet als alle Algorithmen der Standardbibliothek, aber davon rate ich ab. Das würde nämlich zu Verwirrung führen.

freakC++

Hallo MFK,
vielen Dank für deine Hilfe.

Nein, du hörst eins vor der Mitte auf und fängst hinter der Mitte wieder an. Du lässt also das Element an der Mitte-Position aus.

1.) Das verstehe ich nicht so richtig. Das mittige Element kann doch nicht einfach ausgelassen werden. Was verstehe ich da falsch?

2.) Wenn ich mir folgenden Aufruf anschaue:

MergeSort(arr,iBegin,iMitte);
	MergeSort(arr,iMitte,iEnd);

dann würde ich als Laise denken, dass das mittlere Element doppelt genommen wird. Wie ich von dir nun schon erfahren habe, ist das nicht der Fall, doch könntest Du einfach nochmal wiederholfen, warum? Das habe ich leider noch immer nicht so ganz begriffen.

3.) Ich wollte es nun umschreiben (ich werde es aufgrund deines letzten Post nun doch lassen, da Du einfach mehr weißt ), doch nehmen wir es trotzdem einmal an:

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

	int i = iBegin;
	int j = iMitte+1;
	int k = 0;

	int* temp = new int [iBegin-iEnd]; //iBegin-iEnd: Anzahl der Elemente in arr (virtuell)

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

}

Wenn ich nun in der while Schleife < iEnd schreibe, wird dann nicht ein Element ausgelassen? Gleichzeitig darf ich aber auch nicht <= schreiben, da ich sonst beim ganzen Array auf ein nicht vorhandenes Element zugreifen würde. Ist das vielleicht auch der Grund, warum man nicht "iMitte+1" schreiben sollte?

Ich danke dir nochmals und hoffe, dass ich bald alles verstehe!
lg, freakC++

MFK

freakC++ schrieb:

Nein, du hörst eins vor der Mitte auf und fängst hinter der Mitte wieder an. Du lässt also das Element an der Mitte-Position aus.

1.) Das verstehe ich nicht so richtig. Das mittige Element kann doch nicht einfach ausgelassen werden. Was verstehe ich da falsch?

Damit wollte ich ausdrücken, was dein veränderter Code tut. Natürlich sollte es nicht so sein.

freakC++ schrieb:

2.) Wenn ich mir folgenden Aufruf anschaue:
MergeSort(arr,iBegin,iMitte);
	MergeSort(arr,iMitte,iEnd);
dann würde ich als Laise denken, dass das mittlere Element doppelt genommen wird. Wie ich von dir nun schon erfahren habe, ist das nicht der Fall, doch könntest Du einfach nochmal wiederholfen, warum? Das habe ich leider noch immer nicht so ganz begriffen.

Es ist in der C++-Standardbibliothek üblich, dass man bei Algorithmen, die auf Sequenzen (also von/bis) arbeiten, zwei Iteratoren angibt: Einen auf das erste Element, und einen hinter das letze Element. Das ist konsequent durchgezogen, darum geben auch die end-Methoden aller Container einen Iterator hinter die Sequenz zurück, nicht aufs letzte Element.

Deine Sortierfunktion ist genauso angesetzt. Das erkennt man schon daran, dass insgesamt iBegin-iEnd Elemente sortiert werden. Das passt nur, wenn iEnd selbst nicht mit sortiert wird, sonst wäre das eins zu wenig.

Wenn also der iEnd-Parameter ein "eins dahinter"-Parameter ist, dann bewirkt der Aufruf MergeSort(arr,iBegin,iMitte), dass iMitte selbst nicht mit sortiert wird, denn iMitte zeigt ja hinter das letzte zu sortierende Element. Der andere Aufruf MergeSort(arr,iMitte+1,iEnd) sortiert iMitte aber auch nicht

freakC++ schrieb:

Wenn ich nun in der while Schleife < iEnd schreibe, wird dann nicht ein Element ausgelassen?

Richtig.

freakC++ schrieb:

Gleichzeitig darf ich aber auch nicht <= schreiben, da ich sonst beim ganzen Array auf ein nicht vorhandenes Element zugreifen würde. Ist das vielleicht auch der Grund, warum man nicht "iMitte+1" schreiben sollte?

Genau so ist es.

Wenn deine rekursiven Aufruf so richtig sein sollen (also einmal mit +1, einmal ohne), heißt das, dass bis iEnd einschließlich sortiert werden muss. Das hat weitreichende Folgen. Du musst die Funktion anders benutzen: Wenn du ein Array mit 4 Elementen hast, musst du die Funktion mit 0, 3 aufrufen statt mit 0, 4. Die Anzahl der zu sortierenden Elemente in der Funktion erhöht sich um eins.

Das ist möglich, aber eben von der Benutzung anders als alle Algorithmen der Standardbibliothek.

freakC++

Super, dann habe ich es verstanden.

Herzlichen Dank, MFK!

lg, freakC++