Rekursive Merge-Funktion

Thunderstick

Hallo zusammen,

ich muss eine rekursive Funktion (mischen(m,a,n,b,c)) für das Zusammenfügen zweier bereits sortierter Arrays (a mit M Elementen und b mit n Elementen) schreiben.

Beispiel:
a 1 4 5 6 9
b 2 4 11
Ergebnis in c 1 2 4 4 5 6 9 11.

Es sollen also immer die beiden letzten Elemente der Arrays a und b miteinander verglichen werden und die größere Zahl an das Ende des Arrays c kopiert werden.

Soweit so gut, ich konnte diese Aufgabe auch iterativ lösen, jedoch habe ich leider keinen blassen Schimmer, wie ich diese Aufgabe rekursiv lösen soll.
Im Internet habe ich zahlreiche rekursive Lösungen für das eigentliche sortieren von Arrays mit dem Mergesort-Verfahren gefunden. Das eigentliche Zusammenfügen der dabei entstandenen beiden Arrays war aber immer iterativ.

Hier die iterative Funktion, die ich bereits erstellt habe:

void mischen(int n, int a[], int m, int b[], int c[])
{
	int i=0,j=0,gesamtanzahl=m+n;
	int indexA = n-1;
	int indexB = m-1;
	int indexC = gesamtanzahl-1;

	while((indexA > 0) && (indexB > 0))
	{
		if (a[indexA] > b[indexB])
		{
			c[indexC] = a[indexA];
			indexA--;
		}
		else
		{
			c[indexC] = b[indexB];
			indexB--;
		}
		indexC--;
	}

	while (indexA >= 0)
	{
		c[indexC] = a[indexA];
		indexA--;
		indexC--;
	}
	 while (indexB >= 0)
	{
		c[indexC] = b[indexB];
		indexB--;
		indexC--;
	}
}

Kann mir bitte jemand weiterhelfen, wie ich hierfür eine rekursive Funktion erstellen kann? Ich bin langsam am verzweifeln.
Vielen Dank im Voraus.

drakon

Das rekursiv zu lösen halte ich nicht für sinnvoll. Bist du sicher, dass du den merge Schritt rekursiv machen sollst und nicht das ganze Sortierverfahren prinzipiell rekursiv sein soll?

Thunderstick

Das sehe ich ja genau so.
Die Aufgabe ist hier lediglich die beiden sortierten Arrays zusammenzufügen. Und das soll rekursiv gelöst werden.
Ich wollte das heute iterativ gelöst abgeben, das wurde so aber nicht angenommen. Es soll rekursiv sein.

Hier die exakte Aufgabenstellung

Funktion 4 rekursiv: mischen(m,a,n,b,c)
Es sollen die Elemente zweier sortierter Arrays a (m Elemente) und b (n Elemente)
zusammengemischt und in einem Array c sortiert gespeichert werden.
Beispiel: a 1 4 5 6 9 b 2 4 11 Ergebnis in c 1 2 4 4 5 6 9 11.
Dies lässt sich rekursiv sehr leicht programmieren.
Falls a keine Elemente enthält: b nach c kopieren
Falls b keine Elemente enthält: a nach c kopieren.
Ansonsten das Maximum aller Elemente von a und b bestimmen
Anmerkung: da beide Arrays sortiert ist es eines der beiden letzten Elemente
dieses wird an die entsprechende Stelle von c kopiert
dann die übrigen Elemente von a und b (ohne das maximale) nach c mischen.

Beispiel für einen Zwischenschritt:
Beispiel: a 1 4 5 6 9 b 2 4 11 Ergebnis in c .- - - - - 6 9 11.
Maximum der verbliebenen Elemente von a und b: 5 wird nach c kopiert
a 1 4 5 6 9 b 2 4 11 Ergebnis in c .- - - - 5 6 9 11.
Dann ist nur noch der Rest von a: 1 4 und der Rest von b: 2 4 in die ersten 4 Elemente von c zu
mischen.

Also wenn man seinen Kopf verbiegen muss um ein schönes iteratives Problem rekursiv zu lösen, dann find ich auch irgendwie, dass man hier unnötige Kompetenz entwickelt Schließlich ist Rekursion ja toll um von n² auf n logn n zu kommen und nicht um von n auf n log n zu kommen
Der Recursor hat zugeschlagen!

Bashar

Wenn die Studis alles googeln, wo sie mal 5 Minuten nachdenken müssen, hat man ja keine andere Chance, als unrealistische Aufgaben zu stellen

Wobei ich den Tipp hier grenzwertig finde: Warum sollte man die Arrays von hinten nach vorne aufbauen? Von vorn nach hinten ist doch viel natürlicher.

Ach ja @Decimad: Es bleibt natürlich bei O(n+m).

Ja, ist klar Bashar, dass ein Problem nicht "komplizierter" wird, nur weil man es rekursiv löst.
Ich für meinen Teil würde Tail-Rekursion benutzen, also für den Compiler praktisch eine For-Schleife in spe^^

Bashar

Decimad schrieb:

Ja, ist klar Bashar, dass ein Problem nicht "komplizierter" wird, nur weil man es rekursiv löst.

Dann hatte ich dich falsch verstanden, sorry.

krümelkacker

Thunderstick schrieb:

ich muss eine rekursive Funktion [...] für das Zusammenfügen zweier bereits sortierter Arrays [...] schreiben. [...]
void mischen(int n, int a[], int m, int b[], int c[])
Kann mir bitte jemand weiterhelfen, wie ich hierfür eine rekursive Funktion erstellen kann?

Tipp: a, b und c sind Zeiger, die auf das jeweils erste Element der Sequenzen zeigen. Also, im Fall von a und b auf die ersten Elemente der noch zu "mischenden" Sequenzen und c auf den Teil der Sequenz, der noch erstellt werden muss. Gilt n+m>0 könnte ein rekursiever Aufruf mit mischen(?,?,?,?,c+1) durchgeführt werden (Zeigerarithmetik). Mehr verrat ich nicht.

Edit: Aha, ihr sollt das von hinten machen... Gut, dann braucht man Zeigerarithmetik nicht. Die Lösung steht ja schon fast in der Aufgabenstellung!

Stimmt, da steht es ja sogar schon! Gar nicht gelesen^^