rombi - 1 year ago 71

C++ Question

The following code gives me a segmentation fault when run on a 4Gb machine even after i dynamically allocate the space to the array holding 10 million entries. It works fine with 1 million entries i.e. n = 1000000. The following code sorts integer values along with their index value using radix sort. What should i do to make this program work for 10 million entries.?

`int main()`

{

int n=10000000; // 10 million entries

int *arr=new int [n]; // declare heap memory for array

int *arri=new int [n]; // declare heap memory for array index

for(int i=0;i<n;i++) // initialize array with random number from 0-100

{

arr[i]=((rand()%100)+0);

}

for(i=0;i<n;i++) // initialize index position for array

{

arri[i]=i;

}

radixsort(arr, n ,arri);

return 0;

}

// The main function to that sorts arr[] of size n using Radix Sort

void radixsort(int *arr, int n,int *arri)

{ int m=99; //getMax(arr,n,arri);

// Find the maximum number to know number of digits

// Do counting sort for every digit. Note that instead

// of passing digit number, exp is passed. exp is 10^i

// where i is current digit number

for (int exp = 1; m/exp > 0; exp *= 10)

countSort(arr, n, exp,arri);

}

void countSort(int *arr, int n, int exp,int *arri)

{

int output[n],output1[n]; // output array

int i, count[10] = {0};

// Store count of occurrences in count[]

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

{

count[ (arr[i]/exp)%10 ]++;

}

// Change count[i] so that count[i] now contains actual

// position of this digit in output[]

for (i = 1; i < 10; i++)

count[i] += count[i - 1];

// Build the output array

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

{

output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];

output1[count[ (arr[i]/exp)%10 ] - 1] = arri[i];

count[ (arr[i]/exp)%10 ]--;

}

// Copy the output array to arr[], so that arr[] now

// contains sorted numbers according to current digit

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

{

arr[i] = output[i];

arri[i]=output1[i];

}

}

Answer Source

The problem is in `countSort`

. The `output`

and `output1`

arrays are local arrays, not dynamically allocated, and they're too big for local variables. You're also using the C feature of variable-length arrays, which aren't part of standard C++. Change them to:

```
int *output = new int[n];
int *output1 = new int[n];
```

and add

```
delete[] output;
delete[] output1;
```

at the end of the function.