Почему я столкнулся с sigsegv-ошибкой, когда quicksort был запущен для размера массива 10^6 и элементов размером 10^9, но не с помощью mergesort?

Question

Я попытался с итерационным способом и выбрал элемент поворота как последний элемент массива. Я выполнил его на Hacker Earth, который поднял ошибку sigsegv, где размер массива варьировался от 1 до 10^6 и размер элемента массива от 1 до 10^9. Когда я попытался сортировать слияние, он сделал это эффективно, это даже не вызвало ошибки. Как это произошло? Ниже приведен код, который был реализован.

// An iterative implementation of quick sort  /* working*/ 
#include <iostream> 
using namespace std; 
void swap (long int &a, long int &b) 
{ 
    long int t = a; 
    a = b; 
    b = t; 
} 

int partition (int arr[],long int l,long int h) 
{ 
    long int x = arr[h]; 
    long int i = l; 
    long int j=h-1; 
    while(i<j){ 
     if(arr[i]<x){ 
      i++; 
     } 
     if(arr[j]>x){ 
      j--; 
      continue; 
     } 
     if(arr[i]>x&&arr[j]<x){ 
      swap(arr[i],arr[j]); 
      i++; 
      j--; 
     } 
    } 
    swap(arr[i],arr[h]); 
    return i; 
} 
void quickSortIterative (int arr[], int l, long int h) 
{ 
    int stack[2]; 
    int top = -1; 
    stack[ ++top ] = l; 
    stack[ ++top ] = h; 
    while (top >= 0) 
    { 
     h = stack[ top-- ]; 
     l = stack[ top-- ]; 
     long int p = partition(arr, l, h); 
     if (p-1 > l) 
     { 
      stack[ ++top ] = l; 
      stack[ ++top ] = p - 1; 
     } 
     if (p+1 < h) 
     { 
      stack[ ++top ] = p+1; 
      stack[ ++top ] = h; 
     } 
    } 
} 

int main() 
{ 
    long int N; 
    cin>>N; 
    long int i,j; 
    int arr[N]; 
    for(i=0;i<N;i++){ 
     cin>>arr[i]; 
    } 
    quickSortIterative(arr, 0, N - 1); 
    for (i = 0; i < N; ++i){ 
     cout<<arr[i]<<" "; 
    } 
    return 0; 

}

Answer 1

В стеке [2] имеется только место для 2 целых чисел, но код «толкает» более двух значений в стек. Рассмотрим первый цикл, где p-1> l & & p + 1 < h, и в этом случае верхняя часть увеличивается в 4 раза. Вы можете сделать стек вектором или стеком, используя эквивалент push и pop для хранения и загрузки значений.

ИНТ обр [N] также не будет для больших N. Так как это C++, следует использовать:

int * arr = new int[N]; 

вам нужно удалить [] обр в конце основной.

Answer 2

Выделяя большие массивы в локальном переменном является безошибочным способом вызвать переполнение стека — стека в типичной среде выполнения просто не создан для обработки таких вещей.

Вам необходимо выделить свои массивы в куче; например используя std::vector. Ваш код будет более переносимым, поскольку массивы переменной длины не являются частью стандарта C++.