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!

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;
}