Question

This is my code and can you please tell me why it's not working?

By the way, it will work if I reduce 10,000,000 to 1,000,000.

#include <iostream>

using namespace std;

void radixSort(int*a, int n)

{

int intBitSize = sizeof(int)<<3;

int radix = 256;

int mask = radix-1;

int maskBitLength = 8;

  

int *result = new int[n]();

int *buckets = new int[radix]();

int *startIndex = new int[radix]();

  

int flag = 0;

int key = 0;

bool hasNeg = false;

  

while (flag < intBitSize)

{

for (int i = 0; i < n; ++i)

{

key = (a[i] & (mask << flag)) >> flag;

if(key < 0){

key += mask;

hasNeg = true;

}

++buckets[key];

}

  

startIndex[0] = 0;

  

for (int j = 1; j < radix; ++j)

{

startIndex[j] = startIndex[j - 1] + buckets[j - 1];

}

  

for (int i = n-1; i >= 0; --i)

{

key = (a[i] & (mask << flag)) >> flag;

if(key < 0) key += mask;

result[startIndex[key] + --buckets[key]] = a[i];

}

  

memcpy(a,result,n*sizeof(int));

flag += maskBitLength;

}

  

if(hasNeg)

{

int indexOfNeg = 0;

  

for (int i = 0; i < n; i++)

{

if(a[i] < 0) {

indexOfNeg = i;

break;

}

}

  

memcpy(a,result+indexOfNeg,(n-indexOfNeg)*sizeof(int));

memcpy(a+(n-indexOfNeg),result,indexOfNeg*sizeof(int));

}

  

delete[] result;

delete[] buckets;

delete[] startIndex;

}

void sort(int *A, int n)

{

radixSort(A, n);

}

void sort( int *A, int n);

int main()

{

int i, offset, j;

int B[10000000];

time_t t;

srand( (unsigned) time( &t ));

offset = rand()%10000000;

for( i = 0; i< 10000000; i++ )

{

B[i] = ((91*i)%10000000) + offset;

}

printf("Prepared array of 10 million integers; calling sort\n");

sort( B, 10000000 );

printf("finished sort, now check result\n");

for( i=0, j=0; i < 10000000; i++ )

if( B[i] != i+ offset ) j++;

if( j == 0 )

printf("Passed Test\n");

else

printf("Failed Test. %d numbers wrong.\n", j );

}

Answer 1

For the error you are facing, first the solution :

Move the array definition

int B[10000000];

outside the main function.

Reason of segmentation fault :

When the array is defined in main, it takes up space on the stack. Unfortunately, the space allocated by the OS on the stack, is much less as compared to the space allocated to data-segment (where all global variables are allocated).

So, defining the array as global (instead of on stack in main() method), the issue is solved.