# Segmentation fault on big array

2630 views
2

I was using `quicksort` to see how fast it could order big arrays. I ordered one million no problem.. 2 million no problem. 3 million gives a segfault. Some testing reveals it crashes somewhere between 2 million and 2.1 million, and GDB reveals the crash is from the "fill" function.

This is the code:

``````int partition(int v[], int N){

int i, j;
int x = v[N-1];

for(i = 0, j = 0; i < N - 1; i++){
if (v[i] < x) swap(v, j++, i);
}
swap(v, j, N - 1);
return j;
}

void quickSort(int v[], int N){
int p;

if (N > 1){
p = partition(v, N);
quickSort(v, p);
quickSort(v + p + 1, N - p - 1);
}
}

void fill(int v[], int N){
srand(clock());

for(int i = 0; i < N; i++){
v[i] = rand();
}
}

int main() {

int size = 3000000;
int v[size];

fill(v, size);
quickSort(v, size);

for(int i = 0; i < size; i++)
printf("%d ", v[i]);

printf("\n\nDone\n\n");

return 0;
}
``````

Is there any particular reason the code starts crashing at that particular number? Thank you for any answers

8

With `int size = 3000000;int v[size]`, you are creating a local variable on the "stack". The stack is - compared to the heap - rather limited; so `3000000` may exceed the available stack size, whereas `3000`, for example, might not.

To create `v` on the heap, write

``````int *v = malloc(size);
``````

and afterwards, check if you could allocate the desired space:

``````if (!v) {
printf("not enough space.");
return 1;
}
....
``````

posted this