MergeSort- wo ist der Fehler?

[plizzz]

Tag,
ich wollte heute ein kleines Programm und in diesem Programm brauchte ich einen Sortieralgorithmus. Also habe ich mir gedacht, schreibe ich mal MergeSort selbst, sollte kein Problem sein. Allerdings ist es jetzt eins.

Und zwar habe ich folgenden Code geschrieben (mit "Test" in der int main() ) und es kommt einfach nichts Vernünftiges raus.

#include <stdio.h>
#include <malloc.h>

void MergeSort(int *a, int anfang, int ende);
void Merge(int *a, int anfang, int mitte, int ende);

void MergeSort(int *a, int anfang, int ende)
{
	int mitte;
	if(anfang < ende){
	mitte = (anfang+ende)/2;
	MergeSort(a, anfang, mitte);
	MergeSort(a, mitte+1, ende);
	Merge (a, anfang, mitte, ende);
	}
	return;
}

void Merge(int *a, int anfang, int mitte, int ende)
{
	int *tmp = malloc((ende-anfang+1)*sizeof(int));
	int i=0,j=mitte+1,k;

	for(k=0; k<ende-anfang+1; k++){
		if ( (i<=mitte) && ((j>ende) || (a[i] < a[j])) ){
			tmp[k] = a[i++];
		}else{
			tmp[k] = a[j++];
		}
		for (k=0; k<ende-anfang+1; k++){
			a[anfang+k] = tmp[k];
		}
		free(tmp);
	}

	return;
}

int main()
{
	int i;
	int *a;

	a= malloc(10*sizeof(int));
	for(i=0; i<10; i++){
		a[i]=10-i;
	}
	MergeSort(a, 0, 9);
	for(i=0; i<10; i++){
		printf("%i\n", a[i]);
	}
	free(a);
	return 0;
}

Sitze da jetzt schon ewig dran und kann den Fehler einfach nicht finden. Sieht ihn jemand?

Vielen Dank und mit freundlichen Grüßen,

plizzz

[lagalopex]

Erstmal muss i in Zeile 26 bei anfang beginnen und zum anderen solltest du die Schleife in Zeile 34-36 aus der Schleife Zeile 28-38 herausnehmen.

[pointercrash**]

lagalopex schrieb:

... und zum anderen solltest du die Schleife in Zeile 34-36 aus der Schleife Zeile 28-38 herausnehmen.

Das free dabei mitnehmen. malloc() ohne Test auf NULL ist auch ein wenig grenzgängerisch, würd' ich nicht machen ...

[plizzz]

Habs bereinigt, waren zwei recht dumme Fehler. Dass man bei malloc lieber einen Test auf NULL machen sollte, ist mir zwar klar, allerdings kann bei so einem kleinen Programm, das so wenig Speicher beansprucht, ja sowieso nichts schief gehen - oder doch?

Weitere Frage: Ich habe gegen Ende free(a) gemacht. Ist das überhaupt nötig oder gibt das Programm nach Beendigung sowieso jeglichen allokierten Speicher frei?

[µngbd]

allerdings kann bei so einem kleinen Programm, das so wenig Speicher beansprucht, ja sowieso nichts schief gehen - oder doch?

Wenn aber schon vor dem Programmstart kaum mehr Speicher frei ist...?

Weitere Frage: Ich habe gegen Ende free(a) gemacht. Ist das überhaupt nötig oder gibt das Programm nach Beendigung sowieso jeglichen allokierten Speicher frei?

Erfahrungsgemäß geben die C-Libraries den Speicher beim Beenden frei. Aber ich würde mich nicht drauf verlassen. Btw habe ich das Thema gerade hier angeschnitten:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-248872.html

Dort geht der Konsens in die Richtung, immer free() aufzurufen. fricky hat aber sogar ein Beispiel verlinkt, wo man's bleiben lassen kann.

[pointercrash**]

plizzz schrieb:

Habs bereinigt, waren zwei recht dumme Fehler. Dass man bei malloc lieber einen Test auf NULL machen sollte, ist mir zwar klar, allerdings kann bei so einem kleinen Programm, das so wenig Speicher beansprucht, ja sowieso nichts schief gehen - oder doch?

Weitere Frage: Ich habe gegen Ende free(a) gemacht. Ist das überhaupt nötig oder gibt das Programm nach Beendigung sowieso jeglichen allokierten Speicher frei?

Klar kann was schiefgehen. Wenn Du die Umgebung nicht garantieren kannst, solltest Du alle im Sourcelevel abfangbaren Sachen entsprechend behandeln. Der Lohn ist portabler Code, der nicht nur einfach abkackt (und womöglich alles andere mitreißt), sondern mit Hinweis aufs Problem terminiert, wenn mal was nicht stimmt.

µngbd schrieb:

Erfahrungsgemäß geben die C-Libraries den Speicher beim Beenden frei. Aber ich würde mich nicht drauf verlassen. Btw habe ich das Thema gerade hier angeschnitten:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-248872.html

Dort geht der Konsens in die Richtung, immer free() aufzurufen. fricky hat aber sogar ein Beispiel verlinkt, wo man's bleiben lassen kann.

Yep, aber genau DAS war ein Umgebungsproblem, ich mußte ein Programm als Win- DLL aufbereiten. Da man auch nicht genau feststellen kann, was die Umgebung so macht und kann, muß man jede Interaktion mit ihr prüfen. Win wird als Dauerlaufend oder konkret runtergefahren angenommen, das ist was anderes als ein batteriebetriebener Logger.

[µngbd]

Yep, aber genau DAS war ein Umgebungsproblem, ich mußte ein Programm als Win- DLL aufbereiten. Da man auch nicht genau feststellen kann, was die Umgebung so macht und kann, muß man jede Interaktion mit ihr prüfen. Win wird als Dauerlaufend oder konkret runtergefahren angenommen, das ist was anderes als ein batteriebetriebener Logger.

Als ich deinen Post gelesen hatte (kannte ihn vor dem Link nicht), habe ich angefangen darüber nachzudenken, ob man auch auf einer "großen" Kiste so einen Fall konstruieren kann, wenn man sich bemüht. Aber ich bin zu dem Schluss gekommen, daß ich zu wenig Ahnung davon habe.

Falls dir einmal eine Möglichkeit einfällt: lass es mich bitte wissen!

[;fricky]

µngbd schrieb:

Als ich deinen Post gelesen hatte (kannte ihn vor dem Link nicht), habe ich angefangen darüber nachzudenken, ob man auch auf einer "großen" Kiste so einen Fall konstruieren kann, wenn man sich bemüht.

stecker rausziehen?

[plizzz]

Ok, dann werde ich mir jetzt angewöhnen, nach jedem malloc-Aufruf auf den Nullpointer zu überprüfen. Eine Frage habe ich dazu allerdings noch.

Angenommen, ich möchte mir eine Matrix erstellen durch malloc. Also z.B. mit folgendem Code:

int **a;

a=malloc(m*sizeof(int*));
#test

for(i=0; i<m; i++){
    a[i]=malloc(n*sizeof(int));
}
#test

Jetzt teste ich einmal, ob a NULL ist. Muss ich das nun auch bei jedem a[i] testen oder reicht es, wenn ich es beim letzten teste? Die sind ja alle gleich groß und wenn für ein a[i] kein Speicher da gewesen ist, wirds für die danach wohl auch nicht sein - oder (aus irgendwelchen Gründen) doch?

[µngbd]

Nach jedem Aufruf von malloc() kann der Speicher aus sein. Man kann ja nie wissen, was im Hintergrund vor sich geht, außer man hat die ganze Hardware unter Kontrolle. Deshalb jeden Rückgabewert von malloc() prüfen.

Die sind ja alle gleich groß und wenn für ein a[i] kein Speicher da gewesen ist, wirds für die danach wohl auch nicht sein - oder (aus irgendwelchen Gründen) doch?

Hast recht, ist unwahrscheinlich. Aber möglich. Voraussagen kann man das nicht.

[pointercrash**]

plizzz schrieb:

Ok, dann werde ich mir jetzt angewöhnen, nach jedem malloc-Aufruf auf den Nullpointer zu überprüfen. Eine Frage habe ich dazu allerdings noch.
Angenommen, ich möchte mir eine Matrix erstellen durch malloc. Also z.B. mit folgendem Code:

Bei 'ner Matrix ist es schlauer, gleich n*m Elemente anzufordern, weil malloc nicht gerade ein Rennpferd ist.

plizzz schrieb:

Jetzt teste ich einmal, ob a NULL ist. Muss ich das nun auch bei jedem a[i] testen oder reicht es, wenn ich es beim letzten teste? Die sind ja alle gleich groß und wenn für ein a[i] kein Speicher da gewesen ist, wirds für die danach wohl auch nicht sein - oder (aus irgendwelchen Gründen) doch?

Schau' mal, normalerweise heißt ein fehlgeschlagenes malloc(), daß Du irgendwie den Heap korrumpiert hast. Die Stelle müßtest Du dann beim debuggen sowieso explizit finden.
Jetzt denk' Dir aber mal, Du hast ein Programm, das eine Kette optimierbarer Elemente aufbaut und die in den Heap schichtet. Aufm PC heißt das, wenn so 5000 Elemente den Heap belegen, kratzt den das nicht die Bohne. Auf dem Controller mit 128 kB RAM ist nach etwa 600 Elementen der Heap voll (schwankt!) und malloc() schlägt fehl. Das ist aber kein Drama, sondern bedeutet nur, daß ich die Kette abbrechen muß, den Heap abräumen und eine neue Kette starten.

Grundsätzlich ist es wichtig, jeden malloc()/realloc() zu prüfen. Was beim Fehlschlag dann zu tun ist, hängt vom Szenario ab. Hast Du die hiesige FAQ dazu verinnerlicht?

[plizzz]

pointercrash() schrieb:

Bei 'ner Matrix ist es schlauer, gleich n*m Elemente anzufordern, weil malloc nicht gerade ein Rennpferd ist.

Das verstehe ich nicht. Könntest du das bitte noch etwas weiter ausführen?

Die FAQ habe ich jetzt gelesen, danke.

[pointercrash**]

plizzz schrieb:

Das verstehe ich nicht. Könntest du das bitte noch etwas weiter ausführen?

Du willst ein Feld mit N Spalten und M Zeilen, jeder einzelne malloc kostet ziemlich viel Rechenzeit, zumidest an anderen Libfuncs gemessen. Also allozierst Du gleich N * M Elemente und adressierst nach dem Schema gesucht = array[m * N + n], wobei wieder n die Spalte ist, m die Zeile, der realloc geht dann halt nur Zeilenweise.

Es gibt noch eine Möglichkeit, das komlett Heapverwaltungskompatibel zu machen, das hat fricky mal gepostet, aber ich find's grad nimmer ...

[plizzz]

Ah okay, jetzt habe ich es verstanden. Anstelle einer mxn-Matrix nimmt man also einen n*m-Vektor. Hat diese Variante auch irgendwelche Nachteile (abgesehen von der nicht ganz so intuitiven Handhabung) und der Tatsache, dass ein viel größerer Speicherblock frei sein muss?

[Basher_ist_nicht_BashAr]

plizzz schrieb:

Hat diese Variante auch irgendwelche Nachteile (abgesehen von der nicht ganz so intuitiven Handhabung) und der Tatsache, dass ein viel größerer Speicherblock frei sein muss

nö, überhaupt nicht.

[plizzz]

In der FAQ stand das nicht so genau drin, deshalb frage ich nochmal nach. Was sind denn so die gängigen Vorgehensweisen, falls malloc eben doch den Nullpointer zurückgibt? Ich schreibe hier nämlich grade immer schön einen Test, aber ich habe keine Ahnung, was zu tun ist, falls nicht genug Speicher da ist.

[Basher_ist_nicht_BashAr]

plizzz schrieb:

In der FAQ stand das nicht so genau drin, deshalb frage ich nochmal nach. Was sind denn so die gängigen Vorgehensweisen, falls malloc eben doch den Nullpointer zurückgibt? Ich schreibe hier nämlich grade immer schön einen Test, aber ich habe keine Ahnung, was zu tun ist, falls nicht genug Speicher da ist.

^^das ist stark abhängig von den anforderungen. du könntest die aktion zu einem späteren zeitpunkt wiederholen, und/oder einen eintrag ins logfile schreiben, oder das system anhalten, oder statischen 'ersatzspeicher' benutzen, oder dem benutzer eine messagebox vorsetzen, dass er mal halblang machen soll, und/oder dem programmierer eine SMS schicken, oder, oder, und/oder....
kurz; es gibt kein patentrezept. bei systemen, bei denen sowas nicht passieren darf, darfst du kein 'malloc' benutzen.

[Blue-Tiger]

plizzz schrieb:

In der FAQ stand das nicht so genau drin, deshalb frage ich nochmal nach. Was sind denn so die gängigen Vorgehensweisen, falls malloc eben doch den Nullpointer zurückgibt? Ich schreibe hier nämlich grade immer schön einen Test, aber ich habe keine Ahnung, was zu tun ist, falls nicht genug Speicher da ist.

Wenn du selbst keinen Speicher freigeben kannst (was du im Normalfall eben nicht kannst): abbrechen.

Anekdote nebenbei: Ich hab vor ~2 Monaten mal auf einem Grossrechner eine richtig grosse Matrix bearbeiten muessen. Allerdings liefert malloc 0 zurueck. Was mach ich Dummkopf? Statt aufzugeben vermut ich einen Fehler in der Reservierung. Also hab ich die Matrix statt in einem Rutsch (als n*n Matrix) zu allokieren n mal einen n-Vektor reserviert... Was passiert: nachdem ich ~600 GB RAM reserviert hab (die Maschine hatte insgesamt 1 TB) geht der Maschine die Luft aus und gar nix geht mehr. der Rechner muss neugestartet werden, und alle 20 Leute die grad Rechenjobs laufen hatten waren sauer auf mich.
Die Moral von der Geschichte: besser den Speicher auf einmal reservieren, dann kann das System ueberpruefen ob genug Speicher vorhanden ist, und wenn malloc wirklich mal 0 zurueckliefert, kann man das nicht einfach ignorieren. UND: auch wenn malloc nicht 0 zurueckliefert kann man den Rechner durch bloedes Rumallokieren in die Knie zwingen.