Counting Sort - Segmentation fault (core dumped)

[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. (Bis auf die fehlende Effizienz, die der Algorithmus mit sich bringt).

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


// CountingSort ausführen
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); end_t = clock(); end

= end_t - start_t; fflush(stdout);
}
printf("%10d \t %10d \t| %5ld \t %5ld \t %5ld\n", iAnzahl[k], iMaxVal, 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 = 0;
}

// Werte im iCountArray zählen
for (i = 0; i<length; i++)
{
iCountArray[values]++;
}

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

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


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 = ( (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 = rand();


// Reduziere die Zahl auf die 8 least significant Bits mithilfe einer UND-Verknüpfung mit der Bitmaske
uRand = uCreated8Bit & 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;
}