Counting Sort - Segmentation fault (core dumped) [C]

[mrks]

Hallo Zusammen,

ich bin hier neu und möchte euch von meinen neusten Erfahrungen berichten.

Gerade ist mein Versuch, eine Art Zeit-Messung für einen Counting-Sort-Algorithmus durchzuführen. Dass die Zeit bisher noch nicht in Sekunden ausgegeben wird, sei erstmal beiseite gestellt, denn sobald der maximale Wert, der sortiert werden soll auf 128.000.000 wechselt, dumpt der Core und ich nehme an, dass das was mit dem allokierten Speicherplatz zu tun hat, kann mir aber nach gut einer Woche Fehlersuche einfach nicht mehr weiterhelfen. Deshalb komme ich mit meiner Frage mal auf euch zu, in der Hoffnung, ihr könnt mir meinen Fehler aufzeigen.

kurz zum Code: Es ist eine Programmieraufgabe - die Werte habe ich mir nicht selbst ausgesucht. Es werden automatisiert Zufallszahlen erzeugt, die dann vom Algorithmus nach Größe sortiert werden sollen.

Nach dem Ausschlussverfahren habe ich festgestellt, dass der Fehler in:
int* countingSort(int* values, int length, int maxval);
stehen muss. Der BubbleSort, der auch zu der Aufgabe gehört funktioniert tadellos.

Ich zeige euch dazu am besten mal den (aufs wichtigste gekürzten) Code.
Er ist lauffähig, kann also kopiert und kompiliert werden

Vielen herzlichen Dank schonmal, dass ihr euch die Mühe macht!

P.S.
Bitte seht es mir nach, wenn ich gegen einen Verhaltenskodex für Foren verstoßen habe, ich bin nicht so oft in Foren unterwegs.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <time.h>

// Funktionsdeklarationen
void doSortByCounting();

// Countingsort
void testCountingsort(int valueCount, int minVal, int maxVal);
int* countingSort(int* values, int length, int maxval);

// Für Zufallszahl
unsigned int rand32BitInt();
int* createRandomValues(int minval, int maxval, int length);

// Main Funktion
int main()
{
	doSortByCounting();
}

// Ausgabe im Terminal über die Laufzeiten des Sortieralgorithmus
void doSortByCounting()
{
	printf("\n\n\n\t|     Countingsort     |\n");
	printf("\t|----------------------|\n\n");

	int i;
	int j;
	int k;

	// Variablen für die Stoppuhr
	clock_t start_t;
	clock_t end_t, end[3];

	// Arrays für den automatischen Ablauf
		int iAnzahl[6];
		iAnzahl[0] = 1000000;
		iAnzahl[1] = 2000000;
		iAnzahl[2] = 4000000;
		iAnzahl[3] = 8000000;
		iAnzahl[4] = 16000000;
		iAnzahl[5] = 32000000;

		int iMaxVal[2];
		iMaxVal[0] = 1000000;
		iMaxVal[1] = 128000000;

	printf("    length\t     maxVal\t| Messung 1\tMessung 2\tMessung 3\n");
	
	for (i = 0; i <2; i++)
	{
		for (k = 0; k<6; k++)
		{
			for (j = 0; j < 3; j++)
			{
				start_t = clock();	testCountingsort(iAnzahl[k], 0, iMaxVal[i]);	end_t = clock();	end[j] = end_t - start_t;	fflush(stdout);
			}
			printf("%10d \t %10d \t|   %5ld \t  %5ld \t  %5ld\n", iAnzahl[k], iMaxVal[i], end[0], end[1], end[2]);
		}
	}
}
// testCountingsort
void testCountingsort(int valueCount, int minVal, int maxVal)
{
	int *pRandom;
	int *pSorted;
	
	pRandom = createRandomValues(minVal, maxVal, valueCount);
	pSorted = countingSort(pRandom, valueCount, maxVal);
	
	free(pRandom);
	free(pSorted);	
}

// Countingsort
int* countingSort(int* values, int length, int maxval)
{	
	// values sind die Zufallszahlen
	// length bezeichnet die Anzahl der Werte in values
	// maxval ist der größte Wert der Zufallswerte
	
	int i;
	int *pSort;
	int iCountArray[maxval+1];

	// Speicher allokieren
	pSort = (int *) calloc (length, sizeof(int));	
	
	// CountArray leeren
	for (i = 0; i<=maxval; i++)
	{
		iCountArray[i] = 0;
	}
	
	// Werte im iCountArray zählen
	for (i = 0; i<length; i++)
	{
		iCountArray[values[i]]++;
	}

	// Werte im CountArray aufsummieren
	for (i = 1; i<=maxval; i++)
	{
		iCountArray[i] += iCountArray[i-1];
	}

	// Werte aus dem CountArray sortieren und ins iSortedArray einfügen
	for (i = 0 ;i <length; i++)
	{
		pSort[iCountArray[values[i]]-1] = values[i];
		iCountArray[values[i]]--;
	}
	return pSort;
}

// Zufällige Zahl an Bedingungen anpassen
int* createRandomValues(int minval, int maxval, int length)
{
	
	int *pValues;
	double dDouble;
	unsigned int uRand;		// Übergangsvariable, bis die Berechnung hinhaut
	double dRand;			// Übergangsvariable, die uRand zu einer double konvertiert
	double dUint = (double) UINT_MAX;

	// Speicherplatz Allokieren
	pValues = (int *) malloc(length * sizeof(int)); 
	
	// Zufallszahl verrechnen und an die vorgegebenen Werte anpassen
	for (int i = 0; i <length; i++)
	{
		// Funktion Zufallsgenerator aufrufen
		uRand = rand32BitInt();
		
		// Aus dem unsigned int eine double erzeugen
		dRand = (double) uRand;
		
		// Den double-Wert zu einem Wert zwischen 0 und 1 erzeugen
		dDouble = ( dRand / dUint );
		
		// Die Zufallszahl an den gegebenen Wertebereich anpassen
		// Wert zu einem int konvertieren und den Pointer dorthin zeigen lassen.
		pValues[i] = ( (double) maxval+1 - (double) minval ) * dDouble + (double) minval;		
		
	}	
	return pValues;
}

// Zufällige 32-Bit-Zahl erzeugen
unsigned int rand32BitInt()
{	
	// Variablen für Zufallszahlen
	int uCreated8Bit[4];		// 4x  8-Bit Zahl werden mit Bitshifting auf
	unsigned int uCreated32Bit = 0;		// 1x 32-Bit Zahl addiert.
	
	unsigned int uMask = 255;			// Bitmaske für das Reduzieren der Zahlen auf die 8 least significant Bits.
	unsigned int uRand;
	
	
	// Ausgabe zu Testzwecken
	//printf("for-Schleife rand32\n\n");
	
	
	// 4 Zufallszahlen werden erzeugt.
	for(int i = 0; i<4; i++)
	{
		// Erzeuge eine Integer Zufallszahl
		uCreated8Bit[i] = rand();

	
		// Reduziere die Zahl auf die 8 least significant Bits mithilfe einer UND-Verknüpfung mit der Bitmaske
		uRand = uCreated8Bit[i] & uMask;
		
		
		// Summation der 8-Bit-Zahlen auf die 32-Bit-Zahl
		uCreated32Bit += uRand;
		
		
		// Nach der Summation wird die Zahl 8 Bits nach links geschoben - außer bei der letzten.
		if(i<3) uCreated32Bit = (unsigned int) uCreated32Bit<<8;
		
	}	
		
	return uCreated32Bit;
}

 

[Jana309]

Hallo mrks,
willkommen im Forum.

Ich weiß nicht welchen compiler du benutzt, aber bei mir compiliert dein code so nicht, weil ein Array mit nicht konstaner Länge ("int iCountArray[maxval+1]") verwendet wird. Wenn ich die entsprechende Stelle auf dynamische Allokierung ändere, läuft dein Code und ich sehe den gleichen Fehler wie du.
Ich gehe mal davon aus, dass dein compiler irgendwie automatisch dynamisch allokiert?

zum Fehler:
Der Versuch den Speicher für den Array iCountArray zu allokieren schlägt fehl (calloc liefert Null zurück) und die anschließende Verwendung des Array löst den Zugriffsfehler aus.

Ich denke das liegt am Speicherlimit für x86-Anwendungen (unter Windows, auch 64bit-Windows sind das standardmäßig 2GB). An der Stelle, an der die 2GB überschritten werden, tritt der Fehler auf.

Dass 2GB überschritten werden, liegt daran, dass der Speicher von iCountArray zwar allokiert aber nie wieder freigegeben wird.

Wenn man auf x64 umstellt läuft das Programm ohne Fehler durch (benötigt am Ende ca. 10GB RAM, Das meiste davon sind Memoryleaks)

Wenn man den Speicher von iCountArray jedes mal wieder freigibt, läuft das Programm auch als x86-Anwendung fehlerfrei.

hoffe, das hilft dir weiter.

[mrks]

Hallo Jana,

vielen Dank für deine Antwort, sie war sehr hilfreich und ich habe mein Problem lösen können!

ich habe aus dem "int iCountArray[a]" einen Pointer gemacht, speicher allokiert und ihn am Schluss
wieder freigegeben und jetzt läuft es!

Hab ein ganz wundervolles Wochenende!