Ошибка сегментации на большом массиве

Question

Я использовал quicksort, чтобы увидеть, как быстро он может заказывать большие массивы. Я заказал миллион без проблем .. 2 миллиона без проблем. 3 миллиона дают сегфо. Некоторые тесты показывают, что сбой составляет от 2 до 2 миллионов, а GDB показывает, что сбой произошел из-за функции заполнения.

Это код:

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);
  printf("ready\n\n");
  quickSort(v, size);

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

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

  return 0;
}

Есть ли какая-то особая причина, по которой код начинает падать с этого номера? Спасибо за любые ответы

Answer 1

С int size = 3000000;int v[size] вы создаете локальную переменную в «стеке». Стек - по сравнению с кучей - довольно ограничен; поэтому 3000000 может превышать доступный размер стека, тогда как 3000, например, может не превышать.

Чтобы создать v в куче, напишите

int *v = malloc(size);

, а затем проверьте, можете ли вы выделить необходимое пространство:

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